#1007 数据结构 exercise3-循环链表、双链表

数据结构 exercise3-循环链表、双链表

1.p74实验三2.p74实验四3.删除循环单链表中的奇数4.双链表降序排列

1.p74实验三

//双链表基本运算算法 #include <stdio.h> #include <malloc.h> typedef int ElemType; typedef struct DNode //定义双链表结点类型 { ElemType data; struct DNode *prior; //指向前驱结点 struct DNode *next; //指向后继结点 } DLinkNode; void CreateListF(DLinkNode *&L,ElemType a[],int n) //头插法建双链表 { DLinkNode *s; L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点 L->prior=L->next=NULL; for (int i=0;i<n;i++) { s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点 s->data=a[i]; s->next=L->next; //将结点s插在原开始结点之前,头结点之后 if (L->next!=NULL) L->next->prior=s; L->next=s;s->prior=L; } } void CreateListR(DLinkNode *&L,ElemType a[],int n) //尾插法建双链表 { DLinkNode *s,*r; L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点 L->prior=L->next=NULL; r=L; //r始终指向终端结点,开始时指向头结点 for (int i=0;i<n;i++) { s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点 s->data=a[i]; r->next=s;s->prior=r; //将结点s插入结点r之后 r=s; } r->next=NULL; //尾结点next域置为NULL } void InitList(DLinkNode *&L) { L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点 L->prior=L->next=NULL; } void DestroyList(DLinkNode *&L) { DLinkNode *pre=L,*p=pre->next; while (p!=NULL) { free(pre); pre=p; p=pre->next; } free(pre); } bool ListEmpty(DLinkNode *L) { return(L->next==NULL); } int ListLength(DLinkNode *L) { DLinkNode *p=L; int i=0; while (p->next!=NULL) { i++; p=p->next; } return(i); } void DispList(DLinkNode *L) { DLinkNode *p=L->next; while (p!=NULL) { printf("%c ",p->data); p=p->next; } printf("\n"); } bool GetElem(DLinkNode *L,int i,ElemType &e) { int j=0; DLinkNode *p=L; if (i<=0) return false; //i错误返回假 while (j<i && p!=NULL) { j++; p=p->next; } if (p==NULL) return false; else { e=p->data; return true; } } int LocateElem(DLinkNode *L,ElemType e) { int n=1; DLinkNode *p=L->next; while (p!=NULL && p->data!=e) { n++; p=p->next; } if (p==NULL) return(0); else return(n); } bool ListInsert(DLinkNode *&L,int i,ElemType e) { int j=0; DLinkNode *p=L,*s; if (i<=0) return false; //i错误返回假 while (j<i-1 && p!=NULL) { j++; p=p->next; } if (p==NULL) //未找到第i-1个结点 return false; else //找到第i-1个结点p { s=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建新结点s s->data=e; s->next=p->next; //将结点s插入到结点p之后 if (p->next!=NULL) p->next->prior=s; s->prior=p; p->next=s; return true; } } bool ListDelete(DLinkNode *&L,int i,ElemType &e) { int j=0; DLinkNode *p=L,*q; if (i<=0) return false; //i错误返回假 while (j<i-1 && p!=NULL) { j++; p=p->next; } if (p==NULL) //未找到第i-1个结点 return false; else //找到第i-1个结点p { q=p->next; //q指向要删除的结点 if (q==NULL) return false; //不存在第i个结点 e=q->data; p->next=q->next; //从单链表中删除*q结点 if (p->next!=NULL) p->next->prior=p; free(q); //释放q结点 return true; } } int main() { DLinkNode *h; ElemType e; printf("双链表的基本运算如下：\n"); printf("1、初始化双链表h\n"); InitList(h); printf("2、依次采用尾插法插入a,b,c,d,e元素\n"); ListInsert(h,1,'a'); ListInsert(h,2,'b'); ListInsert(h,3,'c'); ListInsert(h,4,'d'); ListInsert(h,5,'e'); printf("3、输出双链表h:"); DispList(h); printf("4、双链表h的长度：%d\n",ListLength(h)); printf("5、双链表h为%s\n",(ListLength(h)?"空":"非空")); GetElem(h,3,e); printf("6、双链表h的第三个元素是：%c\n",e); printf("7、元素a的位置：%d\n",LocateElem(h,'a')); printf("8、在第4个元素位置上插入f元素\n"); ListInsert(h,4,'f'); printf("9、输出双链表h:"); DispList(h); printf("10、删除h的第三个元素\n"); ListDelete(h,3,e); printf("11、输出双链表h:"); DispList(h); printf("12、释放双链表h\n"); DestroyList(h); return 1; }

2.p74实验四

//循环单链表基本运算算法 #include <stdio.h> #include <malloc.h> typedef int ElemType; typedef struct LNode //定义单链表结点类型 { ElemType data; struct LNode *next; } LinkNode; void CreateListF(LinkNode *&L,ElemType a[],int n) //头插法建立循环单链表 { LinkNode *s;int i; L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点 L->next=NULL; for (i=0;i<n;i++) { s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点 s->data=a[i]; s->next=L->next; //将结点s插在原开始结点之前,头结点之后 L->next=s; } s=L->next; while (s->next!=NULL) //查找尾结点,由s指向它 s=s->next; s->next=L; //尾结点next域指向头结点 } void CreateListR(LinkNode *&L,ElemType a[],int n) //尾插法建立循环单链表 { LinkNode *s,*r;int i; L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点 L->next=NULL; r=L; //r始终指向终端结点,开始时指向头结点 for (i=0;i<n;i++) { s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点 s->data=a[i]; r->next=s; //将结点s插入结点r之后 r=s; } r->next=L; //尾结点next域指向头结点 } void InitList(LinkNode *&L) { L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点 L->next=L; } void DestroyList(LinkNode *&L) { LinkNode *p=L,*q=p->next; while (q!=L) { free(p); p=q; q=p->next; } free(p); } bool ListEmpty(LinkNode *L) { return(L->next==L); } int ListLength(LinkNode *L) { LinkNode *p=L;int i=0; while (p->next!=L) { i++; p=p->next; } return(i); } void DispList(LinkNode *L) { LinkNode *p=L->next; while (p!=L) { printf("%c ",p->data); p=p->next; } printf("\n"); } bool GetElem(LinkNode *L,int i,ElemType &e) { int j=0; LinkNode *p; if (L->next!=L) //单链表不为空表时 { if (i==1) { e=L->next->data; return true; } else //i不为1时 { p=L->next; while (j<i-1 && p!=L) { j++; p=p->next; } if (p==L) return false; else { e=p->data; return true; } } } else //单链表为空表时 return false; } int LocateElem(LinkNode *L,ElemType e) { LinkNode *p=L->next; int n=1; while (p!=L && p->data!=e) { p=p->next; n++; } if (p==L) return(0); else return(n); } bool ListInsert(LinkNode *&L,int i,ElemType e) { int j=0; LinkNode *p=L,*s; if (p->next==L || i==1) //原单链表为空表或i==1时 { s=(LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s s->data=e; s->next=p->next; //将结点s插入到结点p之后 p->next=s; return true; } else { p=L->next; while (j<i-2 && p!=L) { j++; p=p->next; } if (p==L) //未找到第i-1个结点 return false; else //找到第i-1个结点p { s=(LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s s->data=e; s->next=p->next; //将结点s插入到结点p之后 p->next=s; return true; } } } bool ListDelete(LinkNode *&L,int i,ElemType &e) { int j=0; LinkNode *p=L,*q; if (p->next!=L) //原单链表不为空表时 { if (i==1) //i==1时 { q=L->next; //删除第1个结点 e=q->data; L->next=q->next; free(q); return true; } else //i不为1时 { p=L->next; while (j<i-2 && p!=L) { j++; p=p->next; } if (p==L) //未找到第i-1个结点 return false; else //找到第i-1个结点p { q=p->next; //q指向要删除的结点 e=q->data; p->next=q->next; //从单链表中删除q结点 free(q); //释放q结点 return true; } } } else return false; } int main() { LinkNode *h ; ElemType e ; printf("循环单链表的基本运算如下：\n") ; printf("(1)初始化循环单链表h\n") ; InitList(h) ; printf("(2)依次采用尾插法插入a,b,c,d,e元素\n") ; ListInsert(h,1,'a') ; ListInsert(h,2,'b') ; ListInsert(h,3,'c') ; ListInsert(h,4,'d') ; ListInsert(h,5,'e') ; printf("(3)输出循环单链表h:"); DispList(h) ; printf("(4)循环单链表h长度：%d\n",ListLength(h)); printf("(5)循环单链表h为%s\n",(ListEmpty(h)?"空":"非空")); printf("(6)循环单链表h的第三个元素：%c\n",e) ; printf("(7)元素a的位置：%d\n",LocateElem(h,'a')) ; printf("(8)在第四个元素位置上插入f元素\n") ; ListInsert(h,4,'f') ; printf("(9)输出循环单链表h："); DispList(h) ; printf("(10)删除h的第三个元素\n") ; ListDelete(h,3,e); printf("(11)输出循环单链表h："); DispList(h) ; printf("(12)释放循环单链表h\n") ; DestroyList(h) ; return 1; }

3.删除循环单链表中的奇数

已知循环单链表中结点值为整数, 要求编写算法删除此链表中的奇数。

#include <stdio.h> #include <stdlib.h> struct ListNode { int data; struct ListNode *next; }; struct ListNode *createlist(); struct ListNode *deleteeven( struct ListNode *head ); void printlist( struct ListNode *head ) { struct ListNode *p = head; while (p) { printf("%d ", p->data); p = p->next; } printf("\n"); } int main() { struct ListNode *head; head = createlist(); head = deleteeven(head); printlist(head); return 0; } typedef struct ListNode *List; struct ListNode *createlist() { //尾插法读入顺序建立链表，-1为结束符 List head=NULL, tail=NULL; int t; scanf("%d",&t); while(t != -1){ List temp = (List)malloc(sizeof(struct ListNode)); temp->data = t; temp->next = NULL; if(tail==NULL) head = tail = temp; else{ tail->next = temp; tail = temp; } scanf("%d",&t); } return head; } struct ListNode *deleteeven( struct ListNode *head ) { List p=head,q; while(head && ((head->data%2)-1)==0){ //保证头结点不是偶数 p = head; head = head->next; free(p); } //head空指针或者指向一个奇数节点，外层循环判断到结尾，内层循环连续删除 p = head; while(p && p->next) { while(p->next &&((p->next->data%2)-1)==0) { q = p->next; p->next = q->next; } p = p->next; } return head; }

4.双链表降序排列

编写算法将双链表中的结点按值降序排列。

#include<stdio.h> #include<stdlib.h> #define N 5 typedef struct node { int data; struct node * next; } ElemSN; ElemSN * Createlink(int a[],int n) { int i; ElemSN * h=NULL, * p; for( i=N-1;i>=0;i--) { p=(ElemSN *)malloc(sizeof(ElemSN)); p->data =a[i]; p->next=h; h=p; } return h; } void printlink(ElemSN * h) { ElemSN * p; for(p=h;p;p=p->next) printf("%d\n",p->data); } ElemSN* SelectSont(ElemSN*h) { ElemSN*p,*q,*Pm,*Qm,*h1; //pq指针联动，Pm最大值指针，Qm最大指针的前一结点 ，h1头结点 h1=NULL; while(h) { //结束条件是头指针为空 for(Pm=q=h,p=h->next;p;q=p,p=p->next) { if(Pm->data>p->data) { Pm=p; Qm=q; } } //for结束，Pm指的是最大值结点 if(Pm-h) Qm->next=Pm->next; //不是头指针 else h=h->next; //是头指针 Pm->next=h1; //最大值放在头结点 h1=Pm; //设置头指针 } return h1; } int main(void) { int a[N]={11,3,81,9,5}; ElemSN * head; head=Createlink(a,9); head=SelectSont(head); printlink(head); }