最近,从新复习了一下数据结构中比较重要的几个部分,现在把自己的成果记录下来,主要就是仿照严蔚敏的《数据结构》(C 语言版),中的例子和后面的习题进行改编的。首先,是单链表的各种实现,其中,包含了一些常考的知识点。例如,单链表的逆置,单链表的合并,找到单链表的中间节点等的算法实现。下面这个是单链表的结构体的定义: 复制代码 代码如下:typedef struct LNode{ ElemType data; struct LNode *next;}LinkList;下面的基本的单链表的操作:其中,有一些宏,没有给出他们的一些定义,者可以通过,严蔚敏的《数据结构》(C 语言版),查看得到。复制代码 代码如下:/* 功能:构建一个空的带头节点的单链表*/Status InitList (struct LNode **L){ (*L) = (struct LNode *)malloc(sizeof(struct LNode)); //产生头节点 if(!*L) exit(OVERFLOW); (*L)->next = NULL; return OK;}/*销毁线性表*/Status DestroyList(struct LNode *L){ struct LNode *q; while(L) { q = L->next; free(L); L = q; } return OK;}/*将L重置为空表*/Status ClearList(struct LNode *L){ LinkList *p,*q; p = L->next; while(p) { q = p->next; free(p); p = q; } L->next = NULL; return OK;}/*判断链表是否为空表*/Status ListEmpty(LinkList *L){ if(L->next) { return FALSE; } else { return TRUE; }}/*返回单链表中元素的个数*/int ListLength(struct LNode *L){ int i=0; LinkList *p = L->next; while(p) { i++; p = p->next; } return i;}/* L为带头节点的单链表的头指针,当第i个元素存在时,其值赋给e,并返回OK */Status GetElem(struct LNode *L,int i,ElemType *e){ int j=1; LinkList *p = L->next; while(p && j<i) { p = p->next; j++; } if(!p || j>i) return ERROR; *e = p->data; return OK;}/*返回L中第一个与e满足关系compare()的数据元素的位序, 若给存在返回值为0,compare()是数据元素的判定函数*/int LocateElem(struct LNode *L,ElemType e,Status(*compare) (ElemType,ElemType)){ int i =0; LinkList *p = L->next; while(p) { i++; if(compare(p->data,e)) return i; p=p->next; } return 0;}复制代码 代码如下:/*所cur_e是L中的数据元素,且给就第一个,则用pre_e返回它的前驱*/Status PriorElem(struct LNode *L,ElemType cur_e,ElemType *pre_e){ LinkList *q,*p=L->next; while(p->next) { q = p->next;//q指向p的后继 if(q->data == cur_e) { *pre_e = p->data; return OK; } p = q; } return INFEASIBLE;}/* 若cur_e是L中的数据元素,且不是最后一个,则用next_e返回它的后继*/Status NextElem(struct LNode *L,ElemType cur_e,ElemType *next_e){ LinkList *p; p = L->next; while(p->next) { if(p->data == cur_e) { * next_e = p->next->data; return OK; } p = p->next; } return INFEASIBLE;}/* 在带头节点的单链表L中的第i个位置之前插入元素e*/Status ListInsert(struct LNode *L,int i,ElemType e){ int j =0; struct LNode *p=L,*s=NULL; while(p && j<i-1) { p=p->next; j++; } if(!p || j>i-1) return ERROR; s = (struct LNode *)malloc(sizeof(struct LNode)); if(!s) printf("malloc error~\n"); // p->next = s; s->data = e; // p->next = s; s->next = p->next; p->next = s; //s->next = NULL; // p = s; return OK;}/*在带头节点的单链表中删除第i个元素,并有e返回其值*/Status ListDelete(LinkList *L,int i,ElemType *e){ LinkList *p=L,*q; int j=0; while(p->next && j< i-1) { p = p->next; j++; } if(!p->next || j>i-1) return ERROR; q = p->next; p->next = q->next; *e = q->data; free(q); return OK; }/* 依次对L的每个元素调用vi(),打印输出语句*/Status ListTraverse(struct LNode *L,void (*vi)(ElemType)){ LinkList *p = L->next; while(p) { vi(p->data); p = p->next; } printf("\n"); return OK;}
精彩评论