第四周

学到了，现在还没整理清楚，顺序表，链表之间的差别。 开始理一下吧。 先上题：

oj1 双链表的基本运算

传送门

输入

5 a b c d e

输出

a b c d e 5 no c 1 a b c f d e a b c f e 初始化

L->prior = L->next = NULL;//双链表 L->next = NULL;//单链表

尾插法

void Createlistr(List*& L, int a[], int n) { List* s, * tail; int i; L = (List*)malloc(sizeof(List));//创建头节点 tail = L;//tail始终指向尾节点，初始时指向头节点 for (i = 0; i < n; i++) { s = (List*)malloc(sizeof(List)); s->data = a[i];//创建存放新元素的结点 tail->next = s;//将s插入到tail之后。尾插法 tail = s;//tail始终指向尾节点 } tail->next = NULL;//因为是尾节点，指针域肯定是NULL }//单链表 /// void CreatelistR(slist*& L, char a[], int n) { slist* s, * tc; int i; L = (slist*)malloc(sizeof(slist)); tc = L; for (i = 0; i < n; i++) { s = (slist*)malloc(sizeof(slist)); s->data = a[i]; tc->next = s; @@@@s->prior = tc;@@@@@ tc = s; } tc->next = NULL; }//双链表，多了一步把prior指针的处理

插入InsElem和DelElem的while循环要找到i-1的元素。

插入

int Inselem(List*& L, int x, int i) { int j = 0;//计数器 List* p = L, * s;//*p=L->next??? if (i <= 0) return 0; while (p != NULL && j < i - 1)//还没找到i-1的结点 { j++; p = p->next; } if (p == NULL)//没找到 return 0; else { s = (List*)malloc(sizeof(List));//创建结点 s->data = x;//给所创建的结点的数值域赋值 s->next = p->next;//先自己抢 p->next = s;//后安顿自己 return 1; } }//单链表 int InsElem(slist*& L, char x, int i) { int j = 0; slist* p = L, * s; if (i <= 0) return 0; while (p != NULL && j < i - 1) { j++; p = p->next; } if (p == NULL) return 0; else { s = (slist*)malloc(sizeof(slist)); s->data = x; %%% s->next = p->next; if (p->next != NULL) p->next->prior = s; s->prior = p; p->next = s;%%%% return 1; } }

删除

int Delelem(List*& L, int x, int i) { int j = 0;//计数器 List* p = L, * q;//p在前，q在后 if (i <= 0) return 0; while (p != NULL && j < i - 1)//还没找到i-1的结点 { j++; p = p->next; } if (p == NULL)//没找到 return 0; else//如果找到位置 { q = p->next;//p前q后 if (q == NULL) return 0;//没有第i个结点，返回0； else { p->next = q->next;//！！！ free(q); return 1; } } } int DelElem(slist*& L, int i) { int j = 0; slist* p = L, * pre; if (i <= 0) return 0; while (p!=NULL && j < i ) { j++; p = p->next; } if (p==NULL) return 0; else { pre = p->prior; if (p->next != NULL) p->next->prior = pre; pre->next = p->next; free(p); return 1; } }

oj第二道

反向输出 传送门

void PDDoutput(node *head){ //反向输出 node *p=head->next; while (p->next!=NULL) //找到最后一个结点 p=p->next; while (p!=L) cout<<p->data<<" ",p=p->prior; //借助prior往前 cout<<endl; }

这里，按着pyx的代码敲while(p!=NULL) 会出错，访问冲突。但是while（p!=L）就是对的。 逻辑就是：上面的while循环到链表的末端，下面的while从尾循环到头。

oj第三道

描述

设计整数双链表的基本访问程序，**删除整数双链表中的重复元素，**多个值相同的元素只保留第一个，并用相关数据进行测试

输入

0 1 2 4 3 2 4 4 0 9 9

输出

0 1 2 4 3 2 4 4 0 9 9 0 1 2 4 3 9

void del(slist*& L, int n)//n是啥 ：线性表表长 { slist* p, * q, * t; p = L->next;//初始时p指向第一个结点。 while (p != NULL) { q = p;//p导入到q t = p->next;//t在p的后面 while (t != NULL) { if (p->data == t->data)//如果前后元素相等， { q->next = t->next;//t先存到q里 t = t->next;//后移 n = n - 1;//后移 } else { q = q->next;//如果前后的元素不相等，直接后移 t = t->next; } } p = p->next;//如果t是最后的元素。p直接后移 }

oj第四道

就第一道，用双链表输出

鬼知道我对比修改了多少次。

#include<iostream> #include<stdlib.h> using namespace std; typedef struct List { char data; struct List* prior, * next; }slist; void Initlist(slist*& L) { L = (slist*)malloc(sizeof(slist)); L->prior = L->next = L; } void displist(slist* L) { slist* p = L->next; while (p != L) { cout << p->data << " "; p = p->next; } printf("\n"); } void CreatelistR(slist*& L, char a[], int n) { slist* s, * tc; int i; L = (slist*)malloc(sizeof(slist)); tc = L; for (i = 0; i < n; i++) { s = (slist*)malloc(sizeof(slist)); s->data = a[i]; tc->next = s; s->prior = tc; tc = s; } tc->next = L; } int getlength(slist*& L) { int i = 0; slist* p = L->next; while (p != L) { i++; p = p->next; } return i; } int getElem(slist* L, int i, char& e) { int j = 1; slist* p = L->next; if (i <= 0) return 0; while (p != L && j < i) { j++; p = p->next; } if (p == L) return 0; else { e = p->data; return e; } } int locate(slist* L, char e) { slist* p = L->next; int i = 1; while (p != L && p->data != e) { p = p->next; i++; } if (p == L) return 0; else return i; } int DelElem(slist*& L, int i) { int j = 1; slist* p = L->next, * q; if (i <= 0) return 0; if (L->next == L) return 0; while (p != L && j < i) { j++; p = p->next; } if (p == L) return 0; else { q = p->prior; p->next->prior = q; q->next = p->next; free(p); return 1; } } int InsElem(slist*& L, char x, int i) { int j = 1; slist* p = L->next, * s,*q;//111 if (i <= 0) return 0; while (p != L && j < i )2222 { j++; p = p->next; } if (p == L&&i>j+1) return 0; else { s = (slist*)malloc(sizeof(slist)); s->data = x; q = p->prior; s->prior = q; q->next = s; p->prior = s; s->next = p; //pre->next->prior = s; /*s->next = pre->next; pre->next = s; s->prior = pre;*/ return 1; } } void DestroyList(slist*& L) { slist* pre = L, * p = pre->next; while (p != L) { free(pre); pre = p; p = p->next;//pre,p同步后移。 } free(pre); } int main() { slist* L; Initlist(L); char a[100]; int n; char e; cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; CreatelistR(L, a, n); displist(L); cout << getlength(L) << endl; if (getlength(L) == 0) cout << "yes"; else cout << "no" << endl; getElem(L, 3, e); cout << e << endl; cout << locate(L, 'a') << endl; InsElem(L, 'f', 4); displist(L); DelElem(L, 5); displist(L); DestroyList(L); return 0; }