順序表數組實現

基本操作,增刪查改

#include <iostream>
#include<vector>
#define MAXSIZE 100
#define ERROR -1
using namespace std;
typedef struct LNode* List;
typedef int Position;//這是給LNode型指針,一個別名 List
struct LNode  {
    int data[MAXSIZE];
    Position Last;//position為int類型
}  ;

/* 初始化列表 */
List MakeEmpty() {//初始化列表操作
    List L;//其含義為struct LNode* L,是定義一個LNode類型的
    L = (List)malloc(sizeof( struct LNode));
    L->Last = -1;
    cout << "sqlist已建立" << endl;
    return L;
}
/* 查找元素*/
Position Find(List L, int X) {
    Position i = 0;
    while (i <= L->Last && L->data[i] != X) {
        //當前位置小于順序表長度,
        //且L所指向元素不是要查找元素X,位置i增加1
        i++;
    }
    if (i > L->Last) {
        return ERROR;
    }
    else {
        return i;
    }
}
/*插入元素*/
bool Insert(List L, int X, Position P) {
    //在位置P插入一個元素,本質就是在L->data[P]寫入
    Position i;
    //先判斷表是否已滿
    if (L->Last==MAXSIZE-1) {
        cout << "表空間已滿" << endl;
        return false;
    }
    //再檢查所插入位置是否在表空間范圍內
    if (P<0 || P>L->Last + 1) {//該表為順序表,那么所有插入元素均需在0-Last+1之間
        cout << "插入位置不合法" << endl;
        return false;
    }
    //若以上兩條件均滿足,則開始插入
    for (i = L->Last; i >= P; i--) {
        //先將位置P后 的元素向后移動,為位置P騰出空間
        L->data[i + 1] = L->data[i];
    }
    //此時L->data[p]可以覆蓋
    L->data[P] = X;
    L->Last++;//表長增加1
    return true;
}
/*刪除元素*/
bool Delete(List L,Position P) {
    Position i;
    if (P<0 || P>L->Last) {//位置p不在表中
        cout << "該位置不在表中" << endl;
        return false;
    }
    for (i = P + 1; i <= L->Last; i++) {
        L->data[i-1] = L->data[i];//此處寫法略復雜

    }
    L->Last--;
    return true;
}

int main() {
    List L=MakeEmpty();
    Insert(L, 0, 0);
    Insert(L, 1, 1);
    Insert(L, 2, 2);
    Insert(L, 3, 3);
    Insert(L, 4, 4);
    cout << Find(L, 2) << endl;
    Delete(L, 3);
    return 0;
}

順序表的鏈表實現

該部分有些混亂,主要原因是在于鏈表有無頭節(jié)點和節(jié)點從0開始計算還是從1開始計算.

#include <iostream>
#include<vector>
using namespace std;
typedef  struct LNode* PtrToLNode;
typedef  PtrToLNode  List;
typedef   PtrToLNode Position ;
/*這里的PtrToLNode事實上是一個LNode*型的指針
   因此后邊的List和Position也是一個LNode*的指針
*/
struct LNode {
    int Data;//元素
    PtrToLNode Next;//指向下一個的指針
};
/*按值查找*/
#define ERROR NULL
Position Find(List L, int X) {
    Position p = L;//p指向List的頭節(jié)點
    while (p&&p->Data!=X)//當P非空且P.data!=X時
    {
        p = p->Next;
    }
    /*
    當p=null或者p->data=x時退出while循環(huán),此時如果未找到X
    則P=NULL ,如果找到了,則P本身指向的就是X的地址
    */
    if (p) {
        return p;
    }
    else {
        return ERROR;
    }
}
/*按序號查找,查找表中第K個元素*/
Position FindKth(List L, int K) {
    Position p = L;//p指向頭節(jié)點
    int i = 1;
    while (p != NULL && i < K) {
        p = p->Next;
        i++;
    }
    if (i == K) {
        return p;
    }
    else {
        return NULL;  
    }
}
/*帶頭結點*/
/*插入元素*/
bool Insert(List L, int X ,Position P) {
    Position tmp, pre;
    /*查找P的前一個結點*/
    for (pre = L; pre && pre->Next != P; pre = pre->Next);
    if (pre ==NULL) {
        cout << "插入位置參數錯誤" << endl;
        return false;
    }
    else {
        /*為新節(jié)點申請內存空間*/
        tmp = (List)malloc(sizeof(struct LNode));
        tmp->Data = X;
        tmp->Next = P;//將tmp后繼指向P
        pre->Next = tmp;//將原來p 的前驅指向tmp
        return true;
    }
}
/*插入元素,在鏈表的某個位置*/
/*無頭結點*/
bool Insert_Kth(List L, int X, int K) {
    Position tmp, pre;
    if (K== 1) {//插在鏈表第一個位置,由于不存在頭節(jié)點
        tmp = (List)malloc(sizeof(struct LNode));
        tmp->Data = X;
        tmp->Next = L->Next;
        L->Next = tmp;
        return true;
    }
    pre = FindKth(L, K);
    if (pre == NULL) {
        cout << "參數K錯誤" << endl;
        return false;

    }
    else {
        tmp = (List)malloc(sizeof(struct LNode));
        tmp->Data = X;
        tmp->Next = pre->Next;
        pre->Next = tmp;
        return true;
    }
}
/*帶頭結點刪除*/

bool Delete(List L, Position P) {
    Position tmp, pre;
    for (pre = L; pre && pre->Next != P; pre = pre->Next);
    if (pre == NULL || P == NULL) {
        /*這里出現兩種情況,當P!=NULL但是不在表范圍內時,pre==NULL;
        當P==NULL時,pre遍歷到最后一個節(jié)點,此時pre->next=NULL==NULL,
        這兩種情況只要出現一種即意味著插入刪除無法進行.
        */
        cout << "刪除位置參數錯誤" << endl;
        return false;
    }
    else {
        /*進行到這一步則意味著參數合法*/
        pre->Next = P->Next;
        free(P);
        return true;
    }
}
/*按序號刪除*/
bool Delete_Kth(List L, int K) {
    Position pre,tmp;
    if (K == 1) {
        tmp = L;
        if (L != NULL) {
            L = L->Next;
        }
        else {//L為空鏈表
            return true;
        }
        free(tmp);
    }
        pre = FindKth(L, K-1);//查找的是第K個節(jié)點的前驅,即第k-1個節(jié)點
        if (pre == NULL) {
            cout << "節(jié)點K不存在" << endl;
            return false;
        }
        else if (pre->Next == NULL) {
            //這種情況下鏈表只有k-1個節(jié)點
            return false;

        }
        else {//這種情況下K存在
            tmp = pre->Next;
            pre->Next = tmp->Next;
            free(tmp);
            return true;
        }
}
/*尾插法建立鏈表-有頭節(jié)點*/
void InitList_R(List& L, int a[], int n) {
    Position pre, tmp;//pre指向的是當前鏈表的終端節(jié)點,tmp為插入元素申請的臨時節(jié)點
    
    L = (List)malloc(sizeof(struct LNode));
    L->Data = n;//頭節(jié)點首元素存表長
    L->Next = NULL;
    pre = L;
    for (int i = 0; i < n;i++) {

        tmp = (List)malloc(sizeof(struct LNode));
        tmp->Data = a[i];
        pre->Next = tmp;//將當前鏈表最后節(jié)點指向新申請的節(jié)點tmp
        pre = pre->Next;//將pre指向最后一個節(jié)點
    }
    pre->Next = NULL;
}
/*頭插法建立鏈表*/
void InitList_L(List& L, int a[], int n) {
    Position tmp;
    L = (List)malloc(sizeof(struct LNode));
    L->Data = n;
    L->Next = NULL;
    for (int i = 0; i < n;i++) {
        tmp = (List)malloc(sizeof(struct LNode));
        tmp->Data = a[i];
        tmp->Next = L->Next;
        L->Next = tmp;
    }
}
void showList(List L) {//針對有頭節(jié)點的鏈表
    Position pre;
    pre = L->Next;
    while (pre != NULL) {
        cout << pre->Data << endl;
        pre = pre->Next;
    }
}
int main() {
    List L;
    L = (List)malloc(sizeof(struct LNode));
    Insert_Kth(L, 1, 1);
    Insert_Kth(L, 2, 2);
    Insert_Kth(L, 3, 3);
    Insert_Kth(L, 4, 4);
    Insert_Kth(L, 5, 3);
    Delete_Kth(L, 3);//插入刪除是從頭節(jié)點開始算的第K個元素,且從1開始
    return 0;
}

兩種合并有序鏈表
遞增

/*有序鏈表合并算法*/
void Merge(List L1, List L2, List& L3) {
    Position  p = L1->Next;//p指向L1的第一個有數據節(jié)點
    Position  q = L2->Next;//q指向L2的第一個有數據節(jié)點
    Position  r = L3;//r指向L3的頭節(jié)點
    while (p != NULL && q != NULL) {//當L1與L2均非空,即兩個鏈表均沒有插完的時候
        if (p->Data <= q->Data) {
            r->Next = p; p = p->Next;//此句將L3指向L1和L2中較小的節(jié)點
            r = r->Next;//此時r->Next==NULL
        }
        else {
            r->Next = q; q = q->Next;
            r = r->Next;
        }
    }
    if (p != NULL) {//當L2插完而L1還沒有插完時,將L1當前節(jié)點直接指向L1剩余節(jié)點即可.
        r->Next = p;
    }
    if (q != NULL) {
        r->Next = q;
    }

遞減

void Merge_Low(List L1, List L2, List& L3) {
    Position p, q;
    p = L1->Next;//p,q分別指向L1,L2的第一個節(jié)點
    q = L2->Next;
    L3->Next = NULL;//在外邊要建一個包含頭節(jié)點的鏈表L3
    Position tmp;//tmp用來指向L3的端
    while (p != NULL && q != NULL) {
        //遞減鏈表與遞增鏈表的不同之處就在于它只是將尾插法改為了頭插法
        if (p->Data <= q->Data) {
            tmp = p;//將tmp指為我們要插入的節(jié)點
            p = p->Next;//將p指向下一個節(jié)點
            tmp->Next = L3->Next;
            L3->Next = tmp;
        }
        else {
            tmp = q;
            q = q->Next;
            tmp->Next = L3->Next;
            L3->Next = tmp;
        }
    }
    //此時L1 L2中有一個鏈表已經插完
    while (p != NULL) {
        tmp = p;//將tmp指為我們要插入的節(jié)點
        p = p->Next;//將p指向下一個節(jié)點
        tmp->Next = L3->Next;
        L3->Next = tmp;
    }
    while (q != NULL) {
        tmp = q;
        q = q->Next;
        tmp->Next = L3->Next;
        L3->Next = tmp;
    }
}