[计算机类论文精品]c语言数据结构双链表源代码.doc
c语言数据结构双链表源代码/*双链表的创建。此双链表要求为带头节点的，为了算法方便特采用了循环双链表。通过编程发现带头节点的也有其不便之处。为了保持表的一直有序性思考如下：1：表的一开始的创建就要有序。2：插入元素后要做到仍然有序。3：删除元素不会改变表的有序性4：所谓有序，即为非降序或者非升序排列。5：为了做到以上几点，考虑到链表的不易排序性质，特设置一个线性表作为输入缓存空间进行事先排序。关于排序的方法有多种，为了快速完成采用了较为简单的插入排序。copyright :yywill 帖请注明，做人要厚道*/#include <stdio.h>typedef struct LNode int data; struct LNode *next; struct LNode *prior;*Link,Position;typedef struct List_Struct /* 头节点 */ Link head,tail; int len; int value; /* 0表示升序/非降序排列，1表示降序/非升序排列 */LinkList,*List;/*/MakeNode(Link p,List l,int e) /* 创建节点 */ List InitList(); p->data=e; l->tail=p;/* 此函数只设置尾节点，因为头节点只要设置一次 */*/List InitList() /* 初始化建立双链表 */ LinkList *l; l=(LinkList *)malloc(sizeof(LinkList); l->len=0; l->head=l->tail;/* 当头节点和尾节点指向同一地址时候表示为空表 */ return l;/*/CreateList(int n,List l,int *e) /* 1.建立一个有序的带表头结点的双链表 */ /* n为元素个数 */int i,elem;Position *p1,*p2;Sort(n,e) ;p1=(Position *)malloc(sizeof(Position);elem=e1 ;MakeNode(p1,l,elem);/* 第一个节点 */p1->next=p1;p1->prior=p1;l->head=p1;l->len=1; if(n=0)return;/* 如果链表只有一个项则不用执行下面的函数，直接退出 */ for(i=2;i<=n;i+) p2=(Position *)malloc(sizeof(Position); elem=ei; MakeNode(p2,l,elem); (l->len)+;/* 表长度计数，每循环一次加一 */ p1->next=p2;p2->next=l->head; l->head->prior=p2;p2->prior=p1;p1=p2; l->value=1;/* 默认为非升序创建 */*/ListTraverse(List l) /* 遍历链表 */int i=0;Link p;p=l->head;printf("("); for(;i<l->len;i+) printf("%d,",p->data); p=p->next ; printf(")");/*/ConListTraverse(List l) /* 反向遍历链表 */int i=0;Link p;p=l->tail;printf("("); for(;i<l->len;i+) printf("%d,",p->data); p=p->prior ; printf(")");/*/Reverse(List l) /* 5.逆置该双链表 */int i=0;Link p1,p2;List l1,l2;p1=l->head;l1=l;p2=l1->head;l1->head=l1->tail;l1->tail=p2; for(;i<l->len;i+) p2=p1->next; p1->next=p1->prior; p1->prior=p2; p1=p1->prior; if(l->value=1)l->value=0; else l->value=1;/*/LocateElem(int i,List l) /* 3.按位置号查找该双链表 */int j,n;Link p;n=l->len;if(i>n&&n<1) printf("nerror!it is not exist!");return ;if(i<(n/2) p=l->head ; for(j=0;j<n-1;j+) p=p->next; printf("nthe elem_value is:%d",p->data); else p=l->tail ; for(;i<n;n-) p=p->prior; printf("nthe elem_value is:%d",p->data); /*/int GetCurElem(int n,List l) /* 4.按结点值查找该双链表 */ /* 如查找成功则返回所在位置，如找不到则返回0 */Link p;int i;p=l->head; for(i=0;i<l->len;i+) if(p->data=n)return i+1; p=p->next; return 0;/*/int InsBefore(Position *p,int e,List l) /* 6.向前插入一个元素 */ /* 1<=n<=表长+1 */Position *s; int i;s=(Position *)malloc(sizeof(Position);s->data=e ;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;l->len=(l->len+1);return 1;/*/int Ins(int e,List l) /* 6.插入一个元素 ,使表仍然保持有序 */Link p,p1,p2;int i;if(l->value=1)/* 降序 */ p=l->head; /* 从头部开始搜寻 */ for(i=1;i<l->len;i+) p=p->next; if(p->data<=e&&e<=l->head->data)InsBefore(p,e,l);return 1; /* e比当前元素大且比头元素（即最大的元素）小 */ else if(l->value=0)/* 升序 */ p=l->tail; /* 从尾处开始搜寻 */ for(i=1;i<l->len;i+) p=p->prior; if(p->data<=e&&e<=l->tail->data)InsBefore(p->next,e,l);return 1; /* e比当前元素大且比尾元素（即最大的元素）小 */ InsTail(e,l);return 1; /* 当上述条件都不满足的时候可以认为，该元素该插入到头节点 */ /* 或者尾节点，这是两种特殊的情况。 */*/InsTail(int e,List l) /* 为了简单算法，全部插入到尾节点，头节电的通过导致连标， */ /* 换算成尾节点的情况计算 */ /* 全部插尾巴 */Link p1,p2;p1=l->tail;if(l->tail->data)<=e&&(l->head->data)<=e) if(l->value=1) Reverse(l) ; /* 降 */ p2=(Position *)malloc(sizeof(Position); p1=l->tail; MakeNode(p2,l,e); (l->len)+;/* 表长度计数，每循环一次加一 */ p1->next=p2;p2->next=l->head; l->head->prior=p2;p2->prior=p1; else if(l->tail->data>=e&&l->head->data>=e) if(l->value=0)Reverse(l); p2=(Position *)malloc(sizeof(Position); p1=l->tail; MakeNode(p2,l,e); p1->next=p2;p2->next=l->head; l->head->prior=p2;p2->prior=p1; /*/int Remove(int i,List l) /* 7.删除指定位置号结点 */ /* i的合法长度为 1<=n<=表长 */ /* 当返回值为零的时候表示通不过合法性审查 */int n,j=1;Link p;p=l->head;n=l->len;if(i<1&&i>n)printf("now!");return 0; for(;j<i;j+) p=p->next; p->prior->next=p->next;p->next->prior=p->prior;l->len=(l->len-1);if(i=l->len)l->tail=p->prior;if(i=1)l->head=p->next;free(p);return 1;/*/Sort(int n,int *elem) /* 为了保持表的有序，将输入保存在线性表中 */ /* 先用插入排序法排序好后再创建双链表 */ int i,j; for(i=2;i<=n;+i) if(elemi>elemi-1) elem0=elemi ; elemi=elemi-1 ; for(j=i-2;elem0>elemj;-j) elemj+1=elemj ; /* 记录后移 */ elemj+1=elem0 ; /*/int RemoveCur(int e,List l) /* 删除某个值的元素，如果该元素不存在则返回0 */ /* 否则返回1，成功 */int i;i=GetCurElem(e,l);if(i=0) return 0;i=Remove(i,l);if(i=0) return 0;else return 1;/*/main()Link p;List l;int e999,i=1,n,elem,j;char c,NO;l=InitList();printf("nplease input the elems of the List:"); for(;) printf("n please input the elems:"); while(scanf("%d",&ei+)!=1) fflush(stdin); i-; printf("nplease input integer:"); /* 防止用户误操作，清除键盘缓冲区，重置输入条件。 */ printf("n any more?:y/n"); for(;) scanf("%c",&c); if(c='y')break; else if(c='n')break; else c='y'continue; if(c='n')break; ; /* 此处输入创建列表 */i=i-1;CreateList(i,l,e);printf("nplease select by NO:");for(j=0;j+)if(j%2=1)printf("n2.ListTraverse");printf("n3.ConListTraverse");printf("n4.insert");printf("n5.LocateElem");printf("n6.GetCurElem");printf("n7.RemoveNO");printf("n8.RemoveCurElem");printf("n9.Reverse");printf("n0.Exit");scanf("%c",&NO); switch(NO) break; case '2':ListTraverse(l);break; case '3':ConListTraverse(l);break; case '4':printf("ninput:");scanf("%d",&elem);Ins(elem,l);break; case '5':printf("ninput:");scanf("%d",&elem);LocateElem(elem,l);break; case '6':printf("ninput:");scanf("%d",&elem);n=GetCurElem(elem,l); if(n=0)printf("nit is not exist!");break; else printf("n the NO is:%d",n);break; case '7':printf("ninput:");scanf("%d",&elem);n=Remove(elem,l); if(n=0)printf("nit is not exist!");break; else break; case '8':printf("ninput:");scanf("%d",&elem);n=RemoveCur(elem,l); if(n=0)printf("nit is not exist!");break; else break; case '9':Reverse(l);break; case '0':exit(); default :;
