数据结构与算法-linklist逆转
#include #include #define ERROR -1 #define OK 1 //定义单链表 typedef char ElemType; typedef struct LNode // 结点类型定义 { ElemType data; struct LNode * next; }LNode, *LinkList;//LinkList为结构指针类型 //定义关于单链表的若干操作 //初始化--建空表 void InitList(LinkList *L) { *L = (LinkList)malloc(sizeof(LNode)); (*L)->next=NULL; } //尾插法建表 void create_tail(LinkList *L, int n) { LNode *p, *last; int i; last=(*L); for(i=1; idata); //往新结点的数据域中存入元素 last->next=p; //将新结点接在最后一个结点的后面 last=p; //新结点成为最后一个结点 } last->next=NULL; } //求单链表的长度 int ListLength(LinkList L) { LNode *p; int length; p=L->next; //p指针指向第一个元素所在的结点 length=0; //用来存放单链表的长度 while( p!=NULL ) //结点存在 { p=p->next; //p指针向后移 length++; //个数增加１个 } return length; } //求特定元素的个数 int Count(LinkList L, ElemType x) { LNode *p; int length; p=L->next; //p指针指向第一个元素所在的结点 length=0; //用来计算特定元素的个数 while( p ) //结点存在 { if( p->data ==x) //如果找到特定元素，则个数加１ length ++; p=p->next; //p指针向后移 } return length; } //在第i个元素前插入 int ListInsert_L(LinkList *L, int i, ElemType e) { LNode *p, *s; int j; p=(*L); j=0; while( p &&jnext; j++; } if(!p || j>i-1) return ERROR; s=(LNode *)malloc(sizeof(LNode)); //产生一新结点 s->data=e; //往新结点中存入元素 s->next=p->next; p->next=s; //新结点接在p结点之后 return OK; } //删除第i个元素 int ListDelete_L(LinkList *L, int i, ElemType *e) { LNode *p,*q; int j; p=(*L); j=0; while(p->next && jnext; j++; } if(!p->next || j>i-1) return ERROR; q=p->next; p->next=q->next; *e=q->data; free(q); //释放要删除的结点 return OK; } void reverse(LinkList *L) { LNode *p,*q,*r; p=(*L)->next; q=p->next; r=q->next; p->next=NULL; while(q!=NULL) { q->next=p; (*L)->next=q; p=q; q=r; if(r!=NULL) r=q->next; else break; } } void main() { LinkList list1; InitList(&list1); create_tail(&list1, 5); LNode *p; for(p=list1->next; p; p=p->next ) printf("%c ",p->data ); printf("\n"); /* printf("\n========================================\n"); printf("\n单链表的长度：%d\n", ListLength(list1)); printf("\n========================================\n"); printf("单链表中元素c的个数：%d\n", Count(list1, 'c')); printf("\n========================================\n"); ListInsert_L(&list1, 3, 'g'); printf("在第3个元素前插入元素g后，单链表中的元素有：\n"); for(p=list1->next; p; p=p->next ) printf("%c ",p->data ); printf("\n"); printf("\n========================================\n"); ElemType e; ListDelete_L(&list1,4, &e); printf("删除第4个元素后，单链表中的元素有：\n"); for(p=list1->next; p; p=p->next ) printf("%c ",p->data ); printf("\n"); printf("删除掉的元素是：%c\n",e); */ reverse(&list1); for(p=list1->next; p; p=p->next ) printf("%c ",p->data ); } //清空内存 scanf("%c", &p->data); //往新结点的数据域中存入元素 last->next=p; //将新结点接在最后一个结点的后面 last=p; //新结点成为最后一个结点 } last->next=NULL; } //求单链表的长度 int ListLength(LinkList L) { LNode *p; int length; p=L->next; //p指针指向第一个元素所在的结点 length=0; //用来存放单链表的长度 while( p!=NULL ) //结点存在 { p=p->next; //p指针向后移 length++; //个数增加１个 } return length; } //求特定元素的个数 int Count(LinkList L, ElemType x) { LNode *p; int length; p=L->next; //p指针指向第一个元素所在的结点 length=0; //用来计算特定元素的个数 while( p ) //结点存在 { if( p->data ==x) //如果找到特定元素，则个数加１ length ++; p=p->next; //p指针向后移 } return length; } //在第i个元素前插入 int ListInsert_L(LinkList *L, int i, ElemType e) { LNode *p, *s; int j; p=(*L); j=0; while( p &&jnext; j++; } if(!p || j>i-1) return ERROR; s=(LNode *)malloc(sizeof(LNode)); //产生一新结点 s->data=e; //往新结点中存入元素 s->next=p->next; p->next=s; //新结点接在p结点之后 return OK; } //删除第i个元素 int ListDelete_L(LinkList *L, int i, ElemType *e) { LNode *p,*q; int j; p=(*L); j=0; while(p->next && jnext; j++; } if(!p->next || j>i-1) return ERROR; q=p->next; p->next=q->next; *e=q->data; free(q); //释放要删除的结点 return OK; } void reverse(LinkList *L) { LNode *p,*q,*r; p=(*L)->next; q=p->next; r=q->next; p->next=NULL; while(q!=NULL) { q->next=p; (*L)->next=q; p=q; q=r; if(r!=NULL) r=q->next; else break; } } void main() { LinkList list1; InitList(&list1); create_tail(&list1, 5); LNode *p; for(p=list1->next; p; p=p->next ) printf("%c ",p->data ); printf("\n"); /* printf("\n========================================\n"); printf("\n单链表的长度：%d\n", ListLength(list1)); printf("\n========================================\n"); printf("单链表中元素c的个数：%d\n", Count(list1, 'c')); printf("\n========================================\n"); ListInsert_L(&list1, 3, 'g'); printf("在第3个元素前插入元素g后，单链表中的元素有：\n"); for(p=list1->next; p; p=p->next ) printf("%c ",p->data ); printf("\n"); printf("\n========================================\n"); ElemType e; ListDelete_L(&list1,4, &e); printf("删除第4个元素后，单链表中的元素有：\n"); for(p=list1->next; p; p=p->next ) printf("%c ",p->data ); printf("\n"); printf("删除掉的元素是：%c\n",e); */ reverse(&list1); for(p=list1->next; p; p=p->next ) printf("%c ",p->data ); }
用户评论
