2.4.3 循环链表(自学）
循环单链表的操作与单列表基本一致，不同之处在于单链表的循环结束条件是p或p->next为空，而循环单链表的判断条件是它们是否等于头指针。
相关代码请看配套资源
3-循环链表.c
创建和遍历
void main(){ LinkList ha; //定义单链表头指针 ha=InitList(); //初始化单链表 CreatByRear(ha); //尾插法创建单链表 OutPut(ha); //输出单链表 }
运行结果如下
2.4.4 双向链表(自学）
结点定义如下
typedef struct dlnode{ DataType data; Struct dlnode *prior,*next; }DLNode,*DLinkList;
1.双向链表中结点的插入操作
设p指向链表中的某结点,s指向待插入的新结点,将s插在p的前面,尤其要注意操作顺序,操作过程如下
①s->prior=p->prior; ② p->prior->next=s; ③s->next=p; ④p->prior=s;
2.双向链表中结点的删除操作
设p指向双向链表中待删除的结点,操作过
程如图所示。具体如下。
①p->prior->next=p->next; ②p->next->prior-p->prior; ③free(p);
相关代码请看配套资源
4-双向链表.c
增删插
void main(){ LinkList ha; //定义单链表头指针 ha=InitList(); //初始化单链表 CreatByRear(ha); //尾插法创建单链表 OutPut(ha); //输出单链表 printf("在第2个位置上插入\n"); Insert(ha,2); OutPut(ha); //输出单链表 printf("在第2个位置上删除\n"); Delete(ha,2); OutPut(ha); //输出单链表 }
运行结果如下
2.4.5 静态链表(自学）
静态链表是用数组实现的，每个数据元素除了存储数据信息外,还要存储逻辑相邻的下一个数据元素在数组中的位置。可见,静态链表是用数组实现的,但是逻辑相邻的数据元素不一定在物理位置上也相邻
图2-21所示是一个静态链表的例子,SL是一个带头结点的单链表,表示了线性表 (a1,a2,,a3,a4,a5)的存储结构。 从头结点的next域得到4,找到结点a1的位置,再从a1的next域得到2,找到a2的位置 ,如此可依次访问此链表中的所有结点。 对于图2-21,最后一个结点a5的下一个元素位置为4,即a1所在的位置, 这又构成一个循环静态链表。
静态链表描述如下。 typedef struct{ DataType data; int next; } SNode; //结点类型 SNode sd[ MAXSIZE]; int SL; //头指针变量
这种链表的结点中也有数据域data和指针域next,与前面所讲链表中的指针不同的是,这里的指针next(整型)是结点在数组中的下标,称为“静态指针”,所以称这种链表为静态链表。通常将静态链表的next域称为“游标”(cursor),也就是用游标来模拟指针。
相关代码请看配套资源
5-静态链表
int main(){ printf("非循环\n"); SNode sd[MAXSIZE]; int SL=4; sd[0].data=0; sd[0].next=SL; Create(sd,SL); //2 2 3 3 1 1 5 5 4 0 //物理位置 int i=0; for(i;i<6;i++){ printf("%d\n",sd[i].data); } //0 5 3 1 2 4 //逻辑位置 OutPut(sd,SL);//2 3 1 5 4 printf("循环\n"); SNode sdX[MAXSIZE]; int SLX=4; sdX[0].data=0; sdX[0].next=SLX; CreateX(sdX,SLX);//2 2 3 3 1 1 5 5 4 4(SLX) //物理位置 int j=0; for(j;j<6;j++){ printf("%d\n",sdX[j].data); } //0 5 3 1 2 4 //逻辑位置 OutPutX(sdX,SLX);//2 3 1 5 4 }
运行结果如下
2.5 顺序表和链表的比较
顺序表查找、遍历简单
链表插入、删除简单
2.6 实例分析与实现
约瑟夫环
相关代码请看配套资源
约瑟夫环.c
int n=0; int m=0; NodeType * pHead = NULL; do{ //人数n超过最大人数,重新输人人数n直至满足条件为止 if(n> MAX){ printf("人数太多,请重新输入!\n"); } printf("请输人人数n(最多%d个):",MAX); scanf( "%d",&n); }while(n > MAX); printf("请输入初始密码m:"); scanf("%d", &m); CreaList(&pHead,n);//创建单向循环链表 printf("\n---------打印循环链表--------\n"); PrntList(pHead);//打印循环链表 printf( "\n打印出队情况--\n"); JosephusOperate(&pHead,m);//运行约瑟夫环问题 return 1;
运行结果如下
一元多项式运算器
相关代码请看配套资源
多项式.c
void main(){ //默认指数递增排序 printf("输入h1\n"); //建立 LinkList h1=CreatByBear(); printf("输出h1\n"); OutPut(h1); printf("\n"); printf("求值\n"); double x; printf("输入x："); scanf("%lf",&x); double r=result(h1,x); printf("%lf\n",r); printf("der\n"); LinkList hder=der(h1); OutPut(hder); printf("\n"); printf("输入h2\n"); //建立 LinkList h2=CreatByBear(); printf("输出h2\n"); OutPut(h2); printf("\n"); printf("add\n"); LinkList hadd=add(h1,h2); OutPut(hadd); printf("\n"); // printf("sub\n"); LinkList hsub=sub(h1,h2); OutPut(hsub); printf("\n"); printf("mul\n"); LinkList hmul=mul(h1,h2); OutPut(hmul); }
