2.數據結構筆記學習--線性表基本操作

• 線性表的結構定義：
  • 順序表的結構定義：

    typedef struct
    {int data[maxSize];  //存放順序表元素的數組，一般用 int A[maxSize];int length;         //存放順序表的長度,一般用 int n;
    }SeqList;

    ?

  • 單鏈表結點定義：

    typedef struct LNode
    {int data;  //存放結點的數據域struct LNode *next;         //指向后繼結點的指針
    }LNode;

    ?

  • 雙鏈表結點定義：

    typedef struct DLNode
    {int data;  //存放結點的數據域struct DLNode *prior;        //指向前驅結點的指針struct DLNode *next;         //指向后繼結點的指針
    }DLNode;

    ?

• 順序表的算法操作：
  • 按元素值的查找算法：

    int LocateElem (SeqList L, int e)
    {int i;for(i=1; i<=L.Length; i++)if(e=L.data[i])return i;return 0;
    }

    ?

  • 插入數據元素的算法：

    //在p的位置插入新的元素e
    int insert(SeqList &L, int p, int e)  //為啥用&L
    {int i;if(p<1 || p>L.length+1 || L.length>maxSize-1)  //范圍不正確return 0;for(i=L.length; i>=p; --i)  // 依次后移L.data[i+1] = L.data[i];++(L.length);return 1;
    }

    ?

  • 初始化順序表：

    //初始化順序表
    void InitList(SeqList &L)
    {L.length = 0;
    }

    ?

  • 求指定位置元素：

    //e返回L中p的元素
    int GetElem (SeqList L, int p,int &e)  //e用引用類型
    {if(p<1||p>L.length)return 0;e = L.data[p];return 1;
    }

    ?

• 單鏈表的算法操作：
  • 尾插法：

    //n個元素存儲在數組a中，尾插法建立鏈表C
    void CreatelistR(LNode *&C, int a[], int n)  //要改變的變量用引用型
    {LNode *s, *r;  //s指向新申請的結點，r指向C的終端結點int i;C = (LNode *)malloc(sizeof(LNode)); //申請C的頭結點空間C->next =NULL;r=C;  //此時的終端結點就是頭結點for(i=1; i<=n; ++i)  //為啥++i，不是i++
        {s = (LNode* )malloc(sizeof(LNode));s->data = a[i];//用新結點接收a的一個元素r->next = s; //r接納新結點r = r->next;//r指向終端結點，以便接納下一個結點
        }r->next = NULL;
    }

  • 頭插法：

    //n個元素存儲在數組a中，頭插法建立鏈表C
    void CreatelistF(LNode *&C, int a[], int n)  //要改變的變量用引用型
    {LNode *s;  int i;C = (LNode *)malloc(sizeof(LNode)); //申請C的頭結點空間C->next =NULL;for(i=1; i<=n; ++i)  //為啥++i，不是i++
        {s = (LNode* )malloc(sizeof(LNode));s->data = a[i];//用新結點接收a的一個元素s->next = C->next; //s所指向的指針域next指向C的開始結點C->next = s;//頭結點的指針域next指向s結點，s成為新的開始結點
        }
    }

• 雙鏈表的算法操作：
  • 尾插法建立雙鏈表

    //尾插法建立雙鏈表
    void CreateDlistR(DLNode *&L, int a[], int n)
    {DLNode *s,*r;int i;L = (DLNode*)malloc(sizeof(DLNode));L->next = NULL;r=L;  // r始終指向終端結點，開始頭結點也是尾結點for(i=1; i<=n; i++){s = (DLNode*)malloc(sizeof(DLNode));s->data = a[i];//將s插入到L的尾部，并且r指向s，這一部分是主要記憶代碼r->next = s;s->prior = r;r = s;}r->next = NULL;}

  • 查找結點算法：

    DLNode* searchNode(DLNode *C, int x)
    {DLNode *p = C->next;while(p!= NULL){if(p->data == x)break;p = p->next;}return p;
    }

  • 插入結點的算法

    s->next = p->next;
    s->prior = p;
    p->next = s;
    s->next->prior = s;  //假如p指向最后一個結點，本行可去

  • 刪除結點的算法：

    q = p->next;
    p->next = q->next;
    q->next->prior = p;
    free(q);

?