数据结构学习笔记02——线性表

void Union(List &La, List Lb) { // 算法2.1// 将所有在线性表Lb中但不在La中的数据元素插入到La中int La_len,Lb_len,i;ElemType e;La_len &＃61; ListLength(La); // 求线性表的长度 Lb_len &＃61; ListLength(Lb);for (i&＃61;1; i<&＃61;Lb_len; i&＃43;&＃43;) {GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给eif (!LocateElem(La, e, equal)) // La中不存在和e相同的数据元素ListInsert(La, &＃43;&＃43;La_len, e); // 插入
}
} // union

void MergeList(List La, List Lb, List &Lc) { // 算法2.2// 已知线性表La和Lb中的元素按值非递减排列。// 归并La和Lb得到新的线性表Lc&＃xff0c;Lc的元素也按值非递减排列。int La_len, Lb_len;ElemType ai, bj; int i&＃61;1, j&＃61;1, k&＃61;0;InitList(Lc);La_len &＃61; ListLength(La); Lb_len &＃61; ListLength(Lb);while ((i <&＃61; La_len) && (j <&＃61; Lb_len)) { // La和Lb均非空
GetElem(La, i, ai);GetElem(Lb, j, bj);if (ai <&＃61; bj) {ListInsert(Lc, &＃43;&＃43;k, ai);&＃43;&＃43;i;} else { ListInsert(Lc, &＃43;&＃43;k, bj);&＃43;&＃43;j;}}while (i <&＃61; La_len) {GetElem(La, i&＃43;&＃43;, ai); ListInsert(Lc, &＃43;&＃43;k, ai);}while (j <&＃61; Lb_len) {GetElem(Lb, j&＃43;&＃43;, bj); ListInsert(Lc, &＃43;&＃43;k, bj);}
} // MergeList

Status ListInsert_Sq(SqList &L, int i, ElemType e) { // 算法2.4// 在顺序线性表L的第i个元素之前插入新的元素e&＃xff0c;// i的合法值为1≤i≤ListLength_Sq(L)&＃43;1ElemType *p;if (i <1 || i > L.length&＃43;1) return ERROR; // i值不合法if (L.length >&＃61; L.listsize) { // 当前存储空间已满&＃xff0c;增加容量ElemType *newbase &＃61; (ElemType *)realloc(L.elem,(L.listsize&＃43;LISTINCREMENT)*sizeof (ElemType));if (!newbase) return ERROR; // 存储分配失败L.elem &＃61; newbase; // 新基址L.listsize &＃43;&＃61; LISTINCREMENT; // 增加存储容量
}ElemType *q &＃61; &(L.elem[i-1]); // q为插入位置for (p &＃61; &(L.elem[L.length-1]); p>&＃61;q; --p) *(p&＃43;1) &＃61; *p;// 插入位置及之后的元素右移*q &＃61; e; // 插入e&＃43;&＃43;L.length; // 表长增1return OK;
} // ListInsert_Sq

Status ListDelete_Sq(SqList &L, int i, ElemType &e) { // 算法2.5// 在顺序线性表L中删除第i个元素&＃xff0c;并用e返回其值。// i的合法值为1≤i≤ListLength_Sq(L)。ElemType *p, *q;if (i<1 || i>L.length) return ERROR; // i值不合法p &＃61; &(L.elem[i-1]); // p为被删除元素的位置e &＃61; *p; // 被删除元素的值赋给eq &＃61; L.elem&＃43;L.length-1; // 表尾元素的位置for (&＃43;&＃43;p; p<&＃61;q; &＃43;&＃43;p) *(p-1) &＃61; *p; // 被删除元素之后的元素左移--L.length; // 表长减1return OK;
} // ListDelete_Sq

int LocateElem_Sq(SqList L, ElemType e,Status (*compare)(ElemType, ElemType)) { // 算法2.6// 在顺序线性表L中查找第1个值与e满足compare()的元素的位序。// 若找到&＃xff0c;则返回其在L中的位序&＃xff0c;否则返回0。int i;ElemType *p;i &＃61; 1; // i的初值为第1个元素的位序p &＃61; L.elem; // p的初值为第1个元素的存储位置while (i <&＃61; L.length && !(*compare)(*p&＃43;&＃43;, e)) &＃43;&＃43;i;if (i <&＃61; L.length) return i;else return 0;
} // LocateElem_Sq

void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) { // 算法2.7// 已知顺序线性表La和Lb的元素按值非递减排列。// 归并La和Lb得到新的顺序线性表Lc&＃xff0c;Lc的元素也按值非递减排列。ElemType *pa,*pb,*pc,*pa_last,*pb_last;pa &＃61; La.elem; pb &＃61; Lb.elem;Lc.listsize &＃61; Lc.length &＃61; La.length&＃43;Lb.length;pc &＃61; Lc.elem &＃61; (ElemType *)malloc(Lc.listsize*sizeof(ElemType));if (!Lc.elem)exit(OVERFLOW); // 存储分配失败pa_last &＃61; La.elem&＃43;La.length-1;pb_last &＃61; Lb.elem&＃43;Lb.length-1;while (pa <&＃61; pa_last && pb <&＃61; pb_last) { // 归并if (*pa <&＃61; *pb) *pc&＃43;&＃43; &＃61; *pa&＃43;&＃43;;else *pc&＃43;&＃43; &＃61; *pb&＃43;&＃43;;}while (pa <&＃61; pa_last) *pc&＃43;&＃43; &＃61; *pa&＃43;&＃43;; // 插入La的剩余元素while (pb <&＃61; pb_last) *pc&＃43;&＃43; &＃61; *pb&＃43;&＃43;; // 插入Lb的剩余元素
} // MergeList

Status GetElem_L(LinkList &L,int i, ElemType &e) { // 算法2.8// L为带头结点的单链表的头指针。// 当第i个元素存在时&＃xff0c;其值赋给e并返回OK&＃xff0c;否则返回ERROR
LinkList p;p &＃61; L->next; int j &＃61; 1; // 初始化&＃xff0c;p指向第一个结点&＃xff0c;j为计数器while (p && j// 顺指针向后查找&＃xff0c;直到p指向第i个元素或p为空p &＃61; p->next; &＃43;&＃43;j;}if ( !p || j>i ) return ERROR; // 第i个元素不存在e &＃61; p->data; // 取第i个元素return OK;
} // GetElem_L

Status ListInsert_L(LinkList &L, int i, ElemType e) { // 算法2.9// 在带头结点的单链线性表L的第i个元素之前插入元素e
LinkList p,s;p &＃61; L; int j &＃61; 0;while (p && j 1) { // 寻找第i-1个结点p &＃61; p->next;&＃43;&＃43;j;} if (!p || j > i-1) return ERROR; // i小于1或者大于表长s &＃61; (LinkList)malloc(sizeof(LNode)); // 生成新结点s->data &＃61; e; s->next &＃61; p->next; // 插入L中p->next &＃61; s;return OK;
} // LinstInsert_L

Status ListDelete_L(LinkList &L, int i, ElemType &e) { // 算法2.10// 在带头结点的单链线性表L中&＃xff0c;删除第i个元素&＃xff0c;并由e返回其值
LinkList p,q;p &＃61; L;int j &＃61; 0;while (p->next && j 1) { // 寻找第i个结点&＃xff0c;并令p指向其前趋p &＃61; p->next;&＃43;&＃43;j;}if (!(p->next) || j > i-1) return ERROR; // 删除位置不合理q &＃61; p->next;p->next &＃61; q->next; // 删除并释放结点e &＃61; q->data;free(q);return OK;
} // ListDelete_L

void CreateList_L(LinkList &L, int n) { // 算法2.11// 逆位序输入&＃xff08;随机产生&＃xff09;n个元素的值&＃xff0c;建立带表头结点的单链线性表L
LinkList p;int i;L &＃61; (LinkList)malloc(sizeof(LNode));L->next &＃61; NULL; // 先建立一个带头结点的单链表for (i&＃61;n; i>0; --i) {p &＃61; (LinkList)malloc(sizeof(LNode)); // 生成新结点p->data &＃61; random(200); // 改为一个随机生成的数字(200以内)p->next &＃61; L->next; L->next &＃61; p; // 插入到表头
}
} // CreateList_L

void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {// 算法2.12// 已知单链线性表La和Lb的元素按值非递减排列。// 归并La和Lb得到新的单链线性表Lc&＃xff0c;Lc的元素也按值非递减排列。
LinkList pa, pb, pc;pa &＃61; La->next; pb &＃61; Lb->next;Lc &＃61; pc &＃61; La; // 用La的头结点作为Lc的头结点while (pa && pb) {if (pa->data <&＃61; pb->data) {pc->next &＃61; pa; pc &＃61; pa; pa &＃61; pa->next;}else { pc->next &＃61; pb; pc &＃61; pb; pb &＃61; pb->next; }}pc->next &＃61; pa ? pa : pb; // 插入剩余段free(Lb); // 释放Lb的头结点
} // MergeList_L

Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e) {//算法2.19// 删除带头结点的双链循环线性表L的第i个元素&＃xff0c;i的合法值为1≤i≤表长
DuLinkList p;if (!(p &＃61; GetElemP_DuL(L, i))) // 在L中确定第i个元素的位置指针preturn ERROR; // p&＃61;NULL, 即第i个元素不存在e &＃61; p->data;p->prior->next &＃61; p->next;p->next->prior &＃61; p->prior;free(p); return OK;
} // ListDelete_DuL

void CreatPolyn(PLinkList &P, int m) { // 算法2.22// 输入m项的系数和指数&＃xff0c;建立表示一元多项式的有序链表P
PLink h, q, s;PElemType e;int i;InitList(P); h &＃61; GetHead(P);e.coef &＃61; 0.0; e.expn &＃61; -1;SetCurElem(h, e); // 设置头结点for (i&＃61;1; i<&＃61;m; &＃43;&＃43;i) { // 依次输入m个非零项// scanf ("%f,%d\n",&e.coef, &e.expn);e.coef &＃61; (float)(random(1, 90) &＃43; random(10)/10.0);if (random(2)) e.coef &＃61; -e.coef;e.expn&＃61;e.expn&＃43;random(1,10); //产生随机的数据&＃xff0c;但是expn值是递增的if (!LocateElem(P, e, q, cmp)) { // 当前链表中不存在该指数项if (MakeNode(s,e)) InsFirst(q, s); // 生成结点并插入链表if(q&＃61;&＃61;P.tail) P.tail&＃61;s;} else i--; // 如果没有产生插入&＃xff0c;则将i值减1
}
} // CreatPolyn

Status PrintfPoly(PLinkList P) {int i&＃61;0;PLink q&＃61;P.head->next;while (q) {if (fabs(q->data.coef) > 0.005) {if (i>0) {if (q->data.coef>0.005) printf(" &＃43; ");else printf(" - ");printf("%.2f", fabs(q->data.coef));} else printf("%.2f", q->data.coef);if (q->data.expn>&＃61;1) printf("x");if (q->data.expn>1) printf("^%d", q->data.expn);}q&＃61;q->next;if (&＃43;&＃43;i % 6 &＃61;&＃61; 0) printf("\n ");}printf("\n");return OK;
}