《数据结构算法整理(C语言版)》由会员分享，可在线阅读，更多相关《数据结构算法整理(C语言版)（49页珍藏版）》请在金锄头文库上搜索。
1、文档供参考，可复制、编制，期待您的好评与关注！ 数据结构（C语言版）第二章 线性表算法2.1void Union(List &La, List Lb) / 算法2.1/ 将所有在线性表Lb中但不在La中的数据元素插入到La中int La_len,Lb_len,i;ElemType e;La_len = ListLength(La); / 求线性表的长度Lb_len = ListLength(Lb);for (i=1; i=Lb_len; i+) GetElem(Lb, i, e); / 取Lb中第i个数据元素赋给eif (!LocateElem(La, e, equal) / La中不存在和e
2、相同的数据元素ListInsert(La, +La_len, e); / 插入 / union算法2.2void MergeList(List La, List Lb, List &Lc) / 算法2.2/ 已知线性表La和Lb中的元素按值非递减排列。/ 归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。int La_len, Lb_len;ElemType ai, bj;int i=1, j=1, k=0;InitList(Lc);La_len = ListLength(La);Lb_len = ListLength(Lb);while (i = La_len) & (j = L
3、b_len) / La和Lb均非空GetElem(La, i, ai);GetElem(Lb, j, bj);if (ai = bj) ListInsert(Lc, +k, ai);+i; else ListInsert(Lc, +k, bj);+j;while (i = La_len) GetElem(La, i+, ai); ListInsert(Lc, +k, ai);while (j = Lb_len) GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / MergeList算法2.3Status InitList_Sq(SqList &L) /
4、 算法2.3/ 构造一个空的线性表L。L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);if (!L.elem) return OK; / 存储分配失败L.length = 0; / 空表长度为0L.listsize = LIST_INIT_SIZE; / 初始存储容量return OK; / InitList_Sq算法2.4Status ListInsert_Sq(SqList &L, int i, ElemType e) / 算法2.4/ 在顺序线性表L的第i个元素之前插入新的元素e，/ i的合法值为1iListLeng
5、th_Sq(L)+1ElemType *p;if (i L.length+1) return ERROR; / i值不合法if (L.length = L.listsize) / 当前存储空间已满，增加容量ElemType *newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType);if (!newbase) return ERROR; / 存储分配失败L.elem = newbase; / 新基址L.listsize += LISTINCREMENT; / 增加存储容量ElemType
6、*q = &(L.elemi-1); / q为插入位置for (p = &(L.elemL.length-1); p=q; -p) *(p+1) = *p;/ 插入位置及之后的元素右移*q = e; / 插入e+L.length; / 表长增1return OK; / ListInsert_Sq算法2.5Status ListDelete_Sq(SqList &L, int i, ElemType &e) / 在顺序线性表L中删除第i个元素，并用e返回其值。/ i的合法值为1iListLength_Sq(L)。ElemType *p, *q;if (iL.length) return ERRO
7、R; / i值不合法p = &(L.elemi-1); / p为被删除元素的位置e = *p; / 被删除元素的值赋给eq = L.elem+L.length-1; / 表尾元素的位置for (+p; p=q; +p) *(p-1) = *p; / 被删除元素之后的元素左移-L.length; / 表长减1return OK; / ListDelete_Sq算法2.6int LocateElem_Sq(SqList L, ElemType e,Status (*compare)(ElemType, ElemType) / 在顺序线性表L中查找第1个值与e满足compare()的元素的位序。/
8、若找到，则返回其在L中的位序，否则返回0。int i;ElemType *p;i = 1; / i的初值为第1个元素的位序p = L.elem; / p的初值为第1个元素的存储位置while (i = L.length & !(*compare)(*p+, e)+i;if (i = L.length) return i;else return 0; / LocateElem_Sq算法2.7void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) / 已知顺序线性表La和Lb的元素按值非递减排列。/ 归并La和Lb得到新的顺序线性表Lc，Lc的元素也
9、按值非递减排列。ElemType *pa,*pb,*pc,*pa_last,*pb_last;pa = La.elem; pb = Lb.elem;Lc.listsize = Lc.length = La.length+Lb.length;pc = Lc.elem = (ElemType *)malloc(Lc.listsize*sizeof(ElemType);if (!Lc.elem)exit(OVERFLOW); / 存储分配失败pa_last = La.elem+La.length-1;pb_last = Lb.elem+Lb.length-1;while (pa = pa_last
10、& pb = pb_last) / 归并if (*pa = *pb) *pc+ = *pa+;else *pc+ = *pb+;while (pa = pa_last) *pc+ = *pa+; / 插入La的剩余元素while (pb next;int j = 1; / 初始化，p指向第一个结点，j为计数器while (p & jnext; +j;if ( !p | ji ) return ERROR; / 第i个元素不存在e = p-data; / 取第i个元素return OK; / GetElem_L算法2.9Status ListInsert_L(LinkList &L, int i
11、, ElemType e) / / 在带头结点的单链线性表L的第i个元素之前插入元素eLinkList p,s;p = L;int j = 0;while (p & j next;+j;if (!p | j i-1) return ERROR; / i小于1或者大于表长s = (LinkList)malloc(sizeof(LNode); / 生成新结点s-data = e; s-next = p-next; / 插入L中p-next = s;return OK; / LinstInsert_L算法2.10Status ListDelete_L(LinkList &L, int i, Elem
12、Type &e) / 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值LinkList p,q;p = L;int j = 0;while (p-next & j next;+j;if (!(p-next) | j i-1) return ERROR; / 删除位置不合理q = p-next;p-next = q-next; / 删除并释放结点e = q-data;free(q);return OK; / ListDelete_L算法2.11void CreateList_L(LinkList &L, int n) / 逆位序输入（随机产生）n个元素的值，建立带表头结点的单链线性表LLinkList p;int i;L = (LinkList)malloc(sizeof(LNode);L-next = NULL; / 先建立一个带头结点的单链表for (i=n; i0; -i) p = (LinkList)malloc(sizeof(LNode); / 生成新结点p-data = random(200); / 改为一个随机生成的数字(200以内)p-next = L-next; L-next = p; / 插入到表头 /
