2.3.5.删除链表中的重复元素
void Delete(LinkList &L) { LNode *p = L->next; while (p) { LNode *post = p->next; //post指向p的下一个结点 while (post && post->data == p->data) { //post存在并且值和p相等时 LNode *temp = post; //temp指向post post = post->next; //post向后移动 p->next = post; //将p的下一个结点修改为post free(temp); } p = p->next; } }
2.3.6.将两个递增链表合并成一个递减链表
void Merge(LinkList &L1, LinkList L2) { LNode *p = L1->next, *q = L2->next, *temp; L1->next = NULL; //L1断链 while (p && q) { if (p->data <= q->data) { //当前p指向的元素更小 temp = p->next; //temp指向p的下一个结点 p->next = L1->next; //将p用头插法插入L1 L1->next = p; p = temp; //p指向temp } else { //当前q指向的元素更小 temp = q->next; q->next = L1->next; L1->next = q; q = temp; } }//while while (p) { //将剩余节点插入L1 temp = p->next; p->next = L1->next; L1->next = p; p = temp; } while (q) { temp = q->next; q->next = L1->next; L1->next = q; q = temp; } return; }
2.3.7.将两个递增链表合并为一个递增链表
LNode *Merge(LinkList L1, LinkList L2) { LNode *p = L1->next, *q = L2->next, *r, *temp; LNode *L = (LNode*)malloc(sizeof(LNode)); L->next = NULL; r = L; while (p && q) { if (p->data <= q->data) { //当前p指向的结点小于等于q temp = p->next; r->next = p; //p尾插法插入L中 r = p; p = temp; } else { temp = q->next; r->next = q; r = q; q = temp; } } while (p) { //插入剩余结点 temp = p->next; r->next = p; r = p; p = temp; } while (q) { temp = q->next; r->next = q; r = q; q = temp; } r->next = NULL; //将r的next指针置空 return L; }
2.3.8.判断链表是否对称
bool ans(LinkList L) { LNode* post = L->prior, * pre = L->next; //前后指针 //表中元素为奇数时，终止条件为两者移动到同一结点 //表中元素为偶数时，终止条件为两者后指针的next指向前指针 while (post != pre && post->next != pre) { if (post->data != pre->data) return false; //前后指针的指针域不相等 pre = pre->next; //前指针前移 post = post->prior; //后指针后移 } //表对称 return true; }
bool ans(LinkList L) { LNode* p = L->next; int len = 0; //记录表中的元素个数 while (p != L) { p = p->next; len++; } int a = (int*)malloc(len * sizeof(int)); //定义跟链表结点个数相等的长度的数组 len = 0; p = L->next while (p != L) { //遍历链表，用数组保存链表中每个结点的值 a[len] = p->next; p = p->next; } //遍历数组，前后指针指向元素的值不相等，返回false for (int i = 0, j = len - 1; i < j; i++, j--) { if (a[i] != a[j]) return false; } return true; }
2.3.9.依次输出链表中结点值最小的元素
void DeleteMin(LinkList &L) { LNode *p = L->next, *ppre = L->next, *min, *minpre; while (L->next != L) { p = L->next; ppre = L; int tempMin = INT_MAX; //当前最小值 while (p != L) { if (p->data < tempMin) { //当前结点值更小，更新最小结点 min = p; minpre = ppre; } //p向后移动 ppre = p; p = p->next; } cout << min->data; //输出最小结点的值 minpre->next = min->next; //删除min结点 free(min); }//while free(L); //删除头结点 }
2.3.10.真题
void ans(LinkList L, int k){ LNode *p = L->link, *q = L->link; for (int i = 0; i < k; i++) p = p->link; //p指针向后移动k个结点 while (p) { p = p->link; q = q->link; } cout << q->data; }
void ans(LinkList str1, LinkList str2) { LNode *p = str1->next, *q = str2->next; int len1 = 0, len2 = 0; while (p) { //遍历str1，得到str1的长度 len1++; p = p->next; } while (q) { //遍历str2，得到str2的长度 len2++; q = q->next; } int len = abs(len1 - len2); //得到两表长度之差 p = str1->next; //重置pq指向第一个结点 q = str2->next; if (len1 >= len2) { //长表向前移动，使得两表剩余元素相等 for (int i = 0; i < len; i++) p = p->next; } else { for (int i = 0; i < len; i++) q = q->next; } while (p) { //遍历剩余结点，找到两者指向的第一个共同结点 if (p == q) return p; p = p->next; q = q->next; } return NULL; //两者没有共同后缀 }
void ans(LinkList &L){ bool A[n + 1]; //长度为n + 1的数组，用来标记该数是否出现过 for (int i = 0; i < n + 1; i++) A[i] = false; //初始化A数组 LNode *p = head->next, *pre = head; while (p) { int t = abs(p->data); //取当前结点值的绝对值 if (A[t]) { //该值出现过，删除该结点 LNode *r = p->next; pre->next = r; free(p); p = r; } else { //该值没有出现过，在数组A中标记该值，p和pre向后移动 A[t] = true; pre = p; p = p->next; } }//while }
void ans(NODE *L) { NODE* p = L->next, *f = L->next, *s = L->next, *q, *t; while (f->next->next && f->next) { //找到前半链的最后一个结点 f = f->next->next; //快指针移动两个结点 s = s->next; //慢指针移动一个结点 } q = s->next; //q指向后半链的第一个结点 s->next = NULL; //前半链后半链断开 LNode* post = (NODE*)malloc(sizeof(NODE)); post->next = NULL; while (q) { //后半链逆置 t = q->next; q->next = post->next; post->next = q; q = t; } q = post->next; //q指向逆置后的后半链的第一个结点 while (q) { r = q->next; //r指向后半链的下一个结点 t = p->next; //t指向前半链下一个插入位置 q->next = p->next; p->next = q; q = r; //重置pq p = t; } }
3.栈
3.1.栈的数据结构定义
3.1.1.顺序栈
#define MAXSIZE 100 typedef struct Stack { int data[MAXSIZE]; int top = -1; }Stack;
3.1.2.链栈
typedef struct LStack { int data; struct LStack *next; }SNode, *LStack;
3.2.顺序栈的操作
3.2.1.栈的初始化
void InitStack (Stack &S) { S.top = -1; }
3.2.1.入栈
bool Push(Stack &S, int key) { if (S.top == MAXSIZE - 1) return false; //栈满 S.data[++top] = key; return true; }
3.2.2.出栈
bool Pop (Stack &S, int &key) { if (S.top == -1) return false; //栈空 key = S.data[top--]; return true; }
3.2.3.判断栈空
bool IsEmpty (Stack S) { if (S.top == -1) return true; else return false; }
3.3.链栈的基本操作
3.3.1.初始化
void InitStack (LStack &S) { SNode *s = (SNode*)malloc(Sizeof(SNode)); S->next = NULL; }
3.3.2.入栈
void Push (LStack &S, int key) { SNode *p = (SNode*)malloc(sizeof(SNode)); p->data = key; p->next = S->next; //头插法 S->next = p; }
3.3.3.出栈
bool Pop (LStack &S, int &key) { if (S->next == NULL) return false; //栈空 SNode *p = S->next; key = p->data; //key保存栈顶元素的值 S->next = p->next; free(p); }
3.3.4.判断栈空
bool IsEmpty(LStack &S) { if (S->next == NULL) return true; else return false; }
