数据结构与算法分析 读书笔记(链表 栈 队列)

1 逆转单链表

``````void ReverseList(List L){
Position P,Q,R;
P = L->Next;//第一个元素
Q = P->Next;//第二个元素
while(Q){
R = Q->Next;//第三个元素开始，暂时保存
Q->Next = L->Next;//第二个元素插入到头节点和第一个元素之间
L->Next = Q;
Q = R;//指针移动到下一个元素，即第三个元素
}
P->Next = NULL;
}
``````

2 通过调整指针的方式交换某两个相邻的元素

• 单链表

``````//交换P和AfterP
void SwapWithNext( Position BeforeP, LinkList L ) {
Position P, AfterP;
P = BeforeP->Next;
AfterP = P->Next;
P->Next = AfterP->Next;
BeforeP->Next = AfterP;
AfterP->Next = P;
}
``````
• 双向链表

``````void SwapWithNext( Position P, List L ){
Position BeforeP, AfterP;
BeforeP = P->Prev;
AfterP = P->Next;

P-&gt;Next = AfterP-&gt;Next;
BeforeP-&gt;Next = AfterP;
AfterP-&gt;Next = P;
P-&gt;Next-&gt;Prev = P;
P-&gt;Prev = AfterP;
AfterP-&gt;Prev = BeforeP;

}
``````

3 已排序的2个链表，求它们的交集

``````void intersection(LinkList L,LinkList P){
Position T1,T2;
T1 = L->Next;
T2 = P->Next;

while(T1 != NULL && T2 != NULL){
if (T1->Elem < T2->Elem){
T1 = T1->Next;
}else if(T1->Elem > T2->Elem){
T2 = T2->Next;
}else{
printf("%d ",T1->Elem);
T1 = T1->Next;
T2 = T2->Next;
}
}
}
``````

4 已排序的2个链表，求并集

``````LinkList Union(LinkList L,LinkList P){
Position T1,T2;
int X;
R = malloc(sizeof(struct Node));
R ->Next = NULL;
T1 = L->Next;
T2 = P->Next;

while(T1 != NULL && T2 != NULL){
if(T1->Elem < T2->Elem){
X = T1->Elem;
T1 = T1->Next;
}else if(T1->Elem > T2->Elem){
X = T2->Elem;
T2 = T2->Next;
}else{
X = T1->Elem;
T1 = T1->Next;
T2 = T2->Next;
}
insert(X,R);
}
if (T1 != NULL){
while(T1){
insert(T1->Elem,R);
T1 = T1->Next;
}
}
if (T2 != NULL){
while(T2){
insert(T2->Elem,R);
T2 = T2->Next;
}
}
return R;
}
``````

5 多项式加法

``````List add(List L1, List L2){
Position P1,P2;
int E,C;
P1 = L1->Next;
P2 = L2->Next;
List result;
result = malloc(sizeof(struct Node));
result ->Next = NULL;

while(P1 != NULL && P2!= NULL){
if(P1->Exp < P2->Exp){
C = P2->Cof;
E = P2->Exp;
P2 = P2->Next;
}else if(P1->Exp > P2->Exp){
C = P1->Cof;
E = P1->Exp;
P1 = P1->Next;
}else{
C = P1->Cof+P2->Cof;
E = P2->Exp;
P1 = P1->Next;
P2 = P2->Next;
}
insert(C,E,result);
}
if(P1!=NULL){
while(P1){
insert(P1->Cof,P1->Exp,result);
P1 = P1->Next;
}
}
if(P2!=NULL){
while(P2){
insert(P2->Cof,P2->Exp,result);
P2 = P2->Next;
}
}
return result;
}
``````

6 多项式乘法

• 暴力的话时间复杂度很高(M^2 N^2)。2个链表的每个项相乘，需要MN，而得到相乘结果后需要在一个链表中搜索，最坏情况也是MN
• 将每一项与一个多项式相乘，并通过维持一个指向当前结果链表位置的指针把结果插入进来，时间复杂度为 (M^2 N)
• O(MN log(MN))时间复杂度：计算所有的MN结果，借助排序算法按照指数排序并合并

``````    List mulp(List L1,List L2){
Position P1,P2,P3;
int cof,exp;
P1 = L1->Next;
P2 = L2->Next;
List Result;//结果链表
Result = malloc(sizeof(struct Node));
Result ->Next = NULL;

for (; P1; P1 = P1->Next){
P3 = Result;
for (; P2; P2 = P2->Next) {
cof = P1->Cof * P2->Cof;//系数相乘
exp = P1->Exp + P2->Exp;//指数相加
//在结果链表中查找某个位置，满足指数的递减规律，即介于2者之间
while(P3->Next != NULL && P3->Next->Exp > exp){
P3 = P3->Next;
}
if (P3->Next==NULL || P3->Next->Exp < exp)
insertforPoly(cof,exp,Result,P3);
else if(P3->Next->Exp == exp)
P3->Next->Cof += cof;
P3 = P3->Next;
}
P2 = L2->Next;//P2循环完后重新指回L2
}
return Result;
}
``````

7 约瑟夫环问题

``````Position delete(int E, List L){
Position P,Pre,Tmp,Next;
P = L->Next;
Pre = FindPrevious(E,L);
if (!IsLast(P,L) ){
Tmp = Pre->Next;//删除Tmp节点
printf("delete %d \n",Tmp->Elem);
Pre->Next = Tmp->Next;
free(Tmp);
}
Next = Pre->Next;
if (Next==L)
Next = Next->Next;
return Next;
}

List Josephus(List L){
int count;
Position P,Next;
P = L->Next;
count = 0;
while(P->Next->Next != P){
if(count == M){//满足删除节点条件，则删除
Next = delete(P->Elem,L);//删除当前节点，返回下一个节点
P = Next;//指向下一个节点
count = 0;//重置count
}
else{//不满足删除节点条件，则指针向后移动，并计算count值。
if (P->Next == L)
P = P->Next->Next;
else
P = P->Next;
count++;
}
}
return L;//返回删除节点后的链表
}
``````

8 检测平衡符号

``````Stack S;
char ch[N]={'[','{','}','(','a','b','c',')'};
S = CreateStack(20);
for (int i = 0; i < N; ++i) {
char c = ch[i];
if (c=='(' || c=='[' || c=='{')
Push(S,c);
if(c == ')' || c==']'|| c=='}'){
if(!match(c, S)){
printf("error: %c\n",c);
break;
}
}
}
if (!IsEmpty(S))
printf("error");
else
printf("success");

int match(char c,Stack S){//判断是否匹配
char s = Pop(S);
if (c==')')
return s=='(';
else if(c==']')
return s=='[';
else if (c=='}')
return s=='{';
}
``````

9 计算后缀表达式

``````Stack S;
char ch[N]={'6','5','2','3','+','8','*','+','3','+','*'};
S = CreateStack(50);
for (int i = 0; i < N; ++i) {
char c = ch[i];
int result = IsDight(c);
if (result)//当前读取的字符是数字，入栈
Push(S,c-'0');
else{//出栈2个数，计算过结果并入栈
int num1,num2;
num1 = Pop(S);
num2 = Pop(S);
switch(c){
case '+':
Push(S,num2+num1);
break;
case '-':
Push(S,num2-num1);
break;
case '*':
Push(S,num2*num1);
break;
case '/':
Push(S,num2/num1);
break;
default:
break;
}
}
}
printf("result: %d ",Pop(S));

int IsDight(char c){
int num = c-'0';
if (num>=0 && num<=9)
return 1;
else
return 0;
}
``````

10 中缀到后缀的转换

``````//实现过程中调用的函数
int IsDight(char c){
int result = c-'0';
if (result>=0 && result<=9)
return 1;
return 0;
}

int higherorequal(char c, char t){
if ((c== '*' || c =='/') && (t=='+'|| t=='-' || t== '*' || t=='/')){//读入* / 栈顶为+/-/*/ /,优先级高或相同
return 1;
}
if((c== '+' || c =='+') && (t=='+'|| t=='-'))//优先级相同
return 1;
return 0;
}

//main函数
char ch[15] = {'1','+','2','*','3','+','(','4','*','5','+','6',')','*','7'};//中缀 1 + 2 * 3 + ( 4 * 5 + 6 ) * 7
//后缀 1 2 3 * + 4 5 * 6 + 7 * +
Stack S;
S = CreateStack(20);
for (int i = 0; i < 15; ++i) {
char c = ch[i];
if (IsDight(c)){//数字，入栈
printf("%c ",c);
}else{//操作符
if (c =='+' || c  == '-' ){
while (higherorequal(Top(S),c)){//判断栈顶元素优先级和读入的操作符的优先级，栈中优先级高或相同时，出栈直到优先级低于当前读取的操作符优先级
printf("%c ",Pop(S));
}
//栈中弹出优先级高或相等的操作符后，再把当前操作符入栈
Push(S,c);
}
if (c=='*' || c=='/'){
if (Top(S)=='('){//如果栈顶是 '(' 优先级最高，不弹出，继续入栈
Push(S,c);
}else if(higherorequal(c,Top(S))) {//栈顶不是 '(',直接入栈
Push(S, c);
}
}
if (c=='('){
Push(S,c);
}
if ( c==')'){//弹出操作符直到 '(',注意处理符号，操作符才输出，括号不输出
char top = Top(S);
while(top){
if (top=='('){
Pop(S);
break;
}
printf("%c ",Pop(S));
top = Top(S);
}
}
}
}
while(!IsEmpty(S))
printf("%c ",Pop(S));
``````

11 队列的实现

``````typedef struct QueueNode * Node;
typedef Node Position;
typedef struct QueueRecord *Queue;

struct QueueNode{
int Elem;
struct QueueNode * Next;
};

struct QueueRecord{
Position Front, Rear;
int Size;
};
``````

``````Queue CreateQueue(){
Queue Q;
Q = malloc(sizeof(struct QueueRecord));
Q->Rear = malloc(sizeof(struct QueueNode));
Q->Front= Q->Rear ;
Q->Rear->Next = NULL;
Q->Size = 0;
return Q;
}

void Enqueue(int X, Queue Q){
Node P;
P = malloc(sizeof(struct QueueNode));
P->Next = NULL;
Q->Rear->Elem = X;
Q->Rear->Next = P;
Q->Rear= P;
Q->Size+1;
}

int Dequeue(Queue Q){
int result;
Node T;
T = Q->Front->Next;
result = Q->Front->Elem;
free(Q->Front);
Q->Front = T;
return result;
}
int main() {
Queue Q;
Q = CreateQueue();
for (int i = 0; i < 5; ++i) {
Enqueue(i+1,Q);
}
for (int j = 0; j < 5; ++j) {
printf("%d ",Dequeue(Q));
}
return 0;
}
``````