只做鱼网站,网络营销分类,wap网站开发公司,企业内部网站设计1、静态链表 用数组描述的链表叫做静态链表#xff0c;这种描述方法叫做游标实现法。
静态链表需要对数组的第一个和最后一个元素作为特殊元素处理#xff0c;不存数据。
最后一个指向第一个有数据的下标地址#xff0c;第一个游标指向第一个没有数据的下标地址。
我们对…1、静态链表 用数组描述的链表叫做静态链表这种描述方法叫做游标实现法。
静态链表需要对数组的第一个和最后一个元素作为特殊元素处理不存数据。
最后一个指向第一个有数据的下标地址第一个游标指向第一个没有数据的下标地址。
我们对数组的第一个和最后一个元素做特殊处理他们的data不存放数据
-我们通常把未使用的数组元素称为备用链表
-数组的第一个元素即下标为0的那个元素的cur就存放备用链表的第一个结点的下标
-数组的最后一个元素即下标为MAXSIZE-1的cur则存放第一个有数值的元素的下标相当于单链表中的头结点作用。
1.1静态链表的初始化
bool InitList(StaticLinkList list)
{int i;for(i0;iMAXSIZE;i)list[i].cur i1;list[MAXSIZE-1].cur 0; //当前链表为空所以最后一个元素的cur为0 return true;
}
1.2静态链表的插入操作
首先是获得空闲分量的下标
int Malloc_SLL(StaticLinkList space)
{int i space[0].cur; //将第一个游标赋值给i也就是第一个空闲的结点的下标赋值i。if(space[0].cur)space[0].cur space[i].cur;return i;
}// 这段代码是给静态链表的第i-1个元素后添加新元素
bool ListInsert(StaticLinkList list,int i,ElemType e)
{int i,j,l;k MAXSIZE-1;if(i 1 || i ListLength() 1)return false;j Malloc_SSL(L); //获取空闲下标 if(j){list[i].data e; //将数据值赋值给要空闲位置 for(l 1;li-1;l)k list[k].cur; //找到第i-1个元素 list[i].cur list[k].cur; //把第i-1个元素的cur赋值给新元素的cur list[i].cur j; //把新元素的下标赋值给第i-1个元素的cur; return true;}return false;
}
1.3静态链表的删除操作
Status ListDelete(StaticLinkList L,int i)
{int j,k;if(i1||iListLength(L)){return ERROR;}k Max_SIZE-1;for(j0;ji-1;j){k L[k].cur; //找出要删除元素的前一个元素的下标}j L[k].cur; //找到要删除元素的下标L[k].cur L[j].cur; //把要删除元素的游标赋值给其前一个元素的游标Free_SLL(L,j); //释放删除元素的内存return OK;
}
void Free_SLL(StaticLinkList space,int j)
{space[j].cur space[0].cur;space[0] j; //删除元素后该位置变为备用链表表头数组第一个元素的游标存储第一个空闲结点的下表
}
int ListLength(StaticLinkList L)
{int j 0;int i L[MaxSIZE-1].cur; //取出有数据的第一个元素的下标while(i){i L[i].cur; //有数据的最后一个元素的游标为0即为数组第一个元素的下标j;}return j;
}
1.4静态链表的优缺点总结
优点
在插入和删除操作时只需要修改游标不需要移动元素从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点
缺点
没有解决连续存储分配数组带来的表长难以确定的问题
失去了顺序存储结构随机存取的特性。
静态链表其实是为了给没有指针的编程语言设计的一种实现单链表功能的方法。
2、循环链表 将单链表中终端结点的指针端由空指针改为指向头结点就使整个单链表形成一个环这种头尾相接的单链表称为单循环链表简称循环链表。
2.1循环链表初始化
/*循环单链表初始化*/
Status Init_CLinklist(CLinklist *L)
{*L(CLinklist)malloc(sizeof(CLNode)); //创建头结点 if(!(*L)) return ERROR; //创建失败返回ERROR (*L)-next*L; //头结点指针指向本身 return OK;
}
2.2循环链表尾插法构建
/*循环单链表的尾插法构建输入data0的时候结束输入*/
void Create_CLinklist(CLinklist *L)
{CLNode *p,*q; //定义链尾节点和新生节点 int flag1,number; //设立旗帜 p *L;while(flag){scanf(%d,number);if( number!0 ){q(CLinklist)malloc(sizeof(CLNode)); //创建新生节点 if(!q) exit(0); //创建失败结束程序 q-datanumber;p-nextq; pq; //这里和单链表的尾插法相同 }else{p-next *L; //尾指针指向头结点 flag0;}}}2.3循环链表插入
/*循环单链表的插入插入错误返回0插入成功返回1*/
Status Insert_CLinklist(CLinklist *L,int i,Elemtype e)
{int j1; CLNode *p,*q; //定义链尾节点和新生节点 p *L;if(i1||p-next*L||iLength_CLinklist(L)) return ERROR; //插入位置小于1空表或大于表长则返回0 while( p-next!*L ji ){pp-next;j;}q(CLinklist)malloc(sizeof(CLNode));q-datae;q-nextp-next;p-nextq;return OK;
} 2.4循环链表删除
/*循环单链表的删除,删除错误返回0删除成功返回1用e返回被删除的元素*/
Status Delete_CLinklist(CLinklist *L,int i,Elemtype *e)
{int j1; CLNode *p,*q;p *L;if(i1||p-next*L||iLength_CLinklist(L)) return ERROR; //删除位置小于1空表或大于表长则返回0while( p-next ! *L ji){pp-next;j;}qp-next;*eq-data;p-nextq-next;free(q); //释放掉删除结点 return OK;
}2.5返回结点所在的位置
/*返回结点所在的位置*/
int search_CLinklist(node *pNode, int elem)
{node *target;int i 1;for(target pNode; target-data ! elem target ! pNode; i){target target-next;}if(target-next pNode) //表中不存在该元素return 0;else return i;
} 2.6约瑟夫问题 算法思想 根据总人数n创建n个结点的循环链表模拟约瑟夫环每个人为链表中的一个结点工作指针从循环链表表头向后移动至第k个结点从当前开始报数 若不满足出列条件工作指针后移继续报数如满足出列条件删除当前结点 算法描述
//n个人围圈报数报m出列最后剩下的是几号
#include stdio.h
#include stdlib.htypedef struct node
{int data;struct node* next;
}node;node* create(int n)
{node* p NULL, * head;head (node*)malloc(sizeof(node));p head;node* s;int i 1;if (0 ! n){while (i n) /*构建循环链表*/{s (node *)malloc(sizeof(node));s-data i;p-next s;p s;}s-next head-next;//s指向第一个结点形成循环链表}free(head); //释放辅助的头结点return s-next;
}
int main()
{int n 41;int m 3;int i;node* p create(n);node* temp;m % n;while (p ! p-next){for (i 1; i m - 1; i){p p-next;}printf(%d-,p-next-data);temp p-next;p-next temp-next;free(temp);p p-next;}printf(%d\n,p-data);return 0;
}
2.7例题
1、实现将两个线性表a1a2...an和b1b2...bm连接成一个线性表a1...anb1...bm的运算。
分析
-若在单链表或头指针表示的单循环链表上做这种链接操作都需要遍历第一个链表找到结点an然后将结点b1链到an的后面其执行时间是On。
-若在尾指针表示的单循环链表上实现则只需修改指针无需遍历其执行时间是O1。
//假设AB为非空循环链表的尾指针
LinkList Connect(LinkList A, LinkList B)
{LinkList p A-next; //保存A表的头结点位置A-next B-next-next;//B表的开始结点链接到A表表尾free(B-next);//释放B表的头结点B-next p;return B; //返回新循环链表的尾指针
}
2、判断单链表中是否有环。
有环的定义是链表的尾结点指向了链表中的某个结点。
判断单链表中是否有环主要有以下两种方法。
方法一
使用p、q两个指针p总是向前走但q每次都从头开始走对于每个结点看p走的步数是否和q一样。如图当p从6走到3时用了6步此时若q从head出发则只需两步就到3因而步数不等出现矛盾存在环。 方法二 使用p、q两个指针p每次向前走一步p每次向前走两步若在某个时候p q则存在环。
3、魔术师发牌问题
魔术师手中有A、2、3……J、Q、K十三张黑桃扑克牌。在表演魔术前魔术师已经将他们按照一定的顺序叠放好有花色的一面朝下。魔术表演过程为一开始魔术师数1然后把最上面的那张牌翻过来是黑桃A然后将其放到桌面上第二次,魔术师数1、2将第一张牌放到这些牌的最下面将第二张牌翻转过来正好是黑桃2第三次魔术师数1、2、3将第1、2张牌依次放到这些牌的最下面将第三张牌翻过来正好是黑桃3……直到将所有的牌都翻出来为止。则原来牌的顺序为
#include stdio.h
#include stdlib.h
#define CardNumber 13
struct card
{int num;struct card *next;
};
//创建循环链表
struct card *Createcard()
{struct card *head NULL, *p NULL;head (struct card *)malloc(sizeof(struct card)); //已申请不为空p head;struct card *pp NULL;for (int i 1; i CardNumber; i){pp (struct card *)malloc(sizeof(struct card));pp-num 0;p-next pp;p pp;}pp-next head-next; //最后一个结点的下一个执行头结点的下一个形成环free(head); //删除头结点因为已经连起来了且头结点本身又没有数据return pp-next;
}
//定义发牌次序
void SendCard(struct card *p)
{int i;int CountNumber 2;struct card *pp NULL;pp p;pp-num 1; //正向第一个结点牌为1while (1){//需要间隔几个数填上for (i 0; i CountNumber; i){pp pp-next;if (pp-num ! 0) //已经放置过且会优先于它被取出{i--; //跳过已经被取走的即该位置有牌的话则下一个位置}}//找到要填充的位置并赋值if (pp-num 0){pp-num CountNumber;CountNumber;if (CountNumber 14){break;}}}
}int main()
{struct card *p Createcard();SendCard(p);printf(扑克牌次序为\n);for (int i 0; i CardNumber; i){printf(黑桃%d , p-num);p p-next;}return 0;
}3、双向链表 双向链表结点结构 typedef struct DulNode
{ElemType Data;struct DulNode* prior; //前驱结点struct DulNode* next; //后继结点
}DuNode,*DuLinkList;
3.1双向链表的插入操作 代码实现
s-next p;
s-prior p-prior;
p-prior-next s;
p-prior s;
3.2双向链表的删除操作 p-prior-next p-next;
p-next-prior p-prior;
free(p);
pNULL;
总结双向链表相对于单链表来说是要更复杂一点每个结点多了一个prior指针对于插入和删除操作的顺序大家要格外小心。 3.3双向循环链表实践
1、要求实现用户输入一个数使得26个字母的排列发生变化例如用户输入3输出结果
DEFGHIJKLMNOPQRSTUVWXYZABC
同时需要支持负数例如用户输入-3输出结果
XYZABCDEFGHIJKLMNOPQRSTUVW
#include stdio.h
#include stdlib.h#define OK 1
#define ERROR 0typedef char ElemType;
typedef int Status;
typedef struct DualNode
{ElemType data;struct DualNode* prior;struct DualNode* next;
}DualNode,*DuLinkList;Status InitList(DuLinkList* L)
{DualNode* p, * q;int i;*L (DuLinkList)malloc(sizeof(DualNode));if (!(*L)){return ERROR;}(*L)-next (*L)-prior NULL;p (*L);for (i 0; i 26; i){q (DualNode*)malloc(sizeof(DualNode));if (!q){return ERROR;}q-data Ai;q-prior p;q-next p-next;p-next q;p q;}p-next (*L)-next;(*L)-next-prior p;(*L) p;return OK;
}void Caesar(DuLinkList* L, int i)
{if (i 0){do{(*L) (*L)-next;} while (--i);}if (i 0){do{(*L) (*L)-prior;} while (i);}
}
int main()
{DuLinkList L;int i,n;InitList(L);printf(请输入一个整数);scanf_s(%d,n);printf(\n);Caesar(L,n);for (i 0; i 26; i){L L-next;printf(%c,L-data);}printf(\n);return 0;
}
