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

标签: Data-Structures


不直接写链表,栈,队列的实现,直接把做课后题目以及想到的或遇到的问题实现了一下,只给出关键代码

1 逆转单链表

这里采用从第二个元素到最后一个元素逐个插入到头节点和第一个节点之间的方式。习题给出的参考代码用的是3个指针,改变当前元素的指针值指向前一个后,向后移动,直到最后一个元素。

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->Next = AfterP->Next;
    BeforeP->Next = AfterP;
    AfterP->Next = P;
    P->Next->Prev = P;
    P->Prev = AfterP;
    AfterP->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;
    LinkList R;
    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 约瑟夫环问题

写约瑟夫环时,不小心判断错了,开始写的先是判断下一个节点是否到达头结点,但是在处理M=0时,遇到问题。注意,先判断是否count已经为M,是则删除当前节点,并指向下一个节点从新开始计数;否则指针移动,注意,移动时需要判断是否为头结点,是则跳过。

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 检测平衡符号

原题给的是 Pascal语言(begin/end, (), {}, []) 笔者实现的省去了begin/end的检测,C语言的比较没有Java的方便,可以自行实现

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 队列的实现

队列的数组实现比较简单,这里给出的是链表。笔者在实现的时候,出现了许多错误,没有决定要不要采用头结点,后来选择没有头结点。 元素入队时,先malloc一个节点,作为下一次插入,而当前元素放在Rear节点中,然后Rear指针移动。 注意要统一方式,先建一个未保存元素的节点,如创建队列时的Front和Rear指针都指向一个节点;入队时就能采用新建节点,加入元素,Rear指针移动。

头文件 queue.h

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;
}