顺序表与链表

October 2, 2020 本文总阅读量次

顺序表与链表

Before-1

顺序表的创立
顺序表的随机初始化（头插法以及尾插法）
顺序表的定位
顺序表插入删除以及定位元素

求顺序表的交集与并集

#include <iostream>
#define List_Size 100
using namespace std;

struct SqList{
    int *elem;
    int len;
    int size;
};

//TODO List

bool InitList(SqList &L);

bool RandInitList(SqList &L,int n);

bool ListInsert(SqList &L,int i,int e);

bool PrintList(SqList L);

bool DeletList(SqList &L,int n);

int LocateElem(SqList L,int elem);

int comp(const void*a,const void*b);

bool IntersectionElem(SqList La,SqList Lb);

SqList *MergeList(SqList La,SqList Lb);

//TODO function

bool InitList(SqList &L){
    L.elem=(int *)malloc(List_Size*sizeof(int));
    if (!L.elem){
        exit(-2);
    }
    L.len = 0;
    L.size = List_Size;
    return 1;
}

bool RandInitList(SqList &L,int n){
    if (n>=0&&n<List_Size&&InitList(L)==1){
        for (int i = 0; i < n; ++i) {
            L.elem[i] = rand()%100;
        }
        L.len = n;
        return 1;
    }
    return 0;
}

bool ListInsert(SqList &L,int i,int e){
    if (i<1||i>L.len + 1){
        return 0;
    }
    if (L.len > L.size){
        int *newbase = (int *)realloc(L.elem,(L.size+1)*sizeof(int));
        if (!newbase)
            exit(-2);
        L.elem = newbase;
        L.size += 1;
    }
    int *q=&(L.elem[i-1]);
    for (int *p = &(L.elem[L.len - 1]); p>=q; --p) {
        *(p+1) = *p;
    }
    *q = e;
    ++L.len;
    return 1;
}

bool PrintList(SqList L){
    for (int i = 0; i < L.len; ++i) {
        cout<<L.elem[i]<<" ";
    }
    cout<<endl;
}

bool DeletList(SqList &L,int n){
    if (n < 1||n>L.len){
        return 0;
    } else{
        for (int i = n; i < L.len; ++i) {
            L.elem[i-1] = L.elem[i];
        }
        L.len--;
        return 1;
    }
}

int LocateElem(SqList L,int elem){
    for (int i = 0; i < L.len; ++i) {
        if (L.elem[i] == elem){
            return i+1;
        }
    }
    return 0;
}

int comp(const void*a,const void*b){
    return *(int*)a-*(int*)b;
}

SqList *MergeList(SqList La,SqList Lb){
    SqList L;
    InitList(L);
    int i=0,j=0,k=0;
    while ((i < La.len)&&(j < Lb.len)){
        if (La.elem[i]<Lb.elem[j]){
            L.elem[k] = La.elem[i];
            i++;
            k++;
        } else{
            L.elem[k] = Lb.elem[j];
            j++;
            k++;
        }
    }
    if (i == La.len){
        for (int l = j; l < Lb.len; ++l) {
            L.elem[k++] = Lb.elem[l];
        }
    } else{
        for (int l = i; l < La.len; ++l) {
            L.elem[k++] = La.elem[l];
        }
    }
    L.len = La.len + Lb.len;
    return &L;
}

bool IntersectionElem(SqList La,SqList Lb){
    int Min = min(La.len,Lb.len),flag= false;
    if (Min == La.len){
        for (int i = 0; i < La.len; ++i) {
            for (int j = 0; j < Lb.len; ++j) {
                if (La.elem[i] == Lb.elem[j]){
                    if (flag){
                        printf("%d ",La.elem[i]);
                        break;
                    } else{
                        flag = true;
                        printf("交集元素为：\n");
                        printf("%d ",La.elem[i]);
                        break;
                    }
                }
            }
        }
    } else{
        for (int i = 0; i < Lb.len; ++i) {
            for (int j = 0; j < La.len; ++j) {
                if (Lb.elem[i] == La.elem[j]){
                    if (flag){
                        printf("%d ",Lb.elem[i]);
                        break;
                    } else{
                        flag = true;
                        printf("交集元素为：\n");
                        printf("%d ",Lb.elem[i]);
                        break;
                    }
                }
            }
        }
    }
    return flag;
}

//TODO Main Function

int main() {
    int n,oper,insert_loc,insert_elem,delet_loc,find_elem;
    SqList La,Lb;
    printf("开始初始化，输入元素个数：\n");
    cin>>n;
    if (RandInitList(La,n)&&(RandInitList(Lb,n))){
        printf("随机初始化成功,list为：\n");
        PrintList(La);
        PrintList(Lb);
    } else{
        printf("初始化失败\n");
    }
    do {
        printf("__________________\n"
               "输入操作：\n"
               "1:插入\n"
               "2:删除\n"
               "3:查找\n"
               "4:排序\n"
               "5:合并\n"
               "6:交集\n"
               "0:退出\n"
               "___________________\n");
        scanf("%d",&oper);
        switch (oper) {
            case 1:{
                printf("输入插入的位置以及插入的元素：");
                scanf("%d %d",&insert_loc,&insert_elem);
                if (ListInsert(La,insert_loc,insert_elem)){
                    printf("插入成功，list为：\n");
                    PrintList(La);
                } else{
                    printf("插入失败\n");
                }
                break;
            }
            case 2:{
                printf("请输入删除的位置：\n");
                scanf("%d",&delet_loc);
                if (DeletList(La,delet_loc)){
                    printf("删除成功，删除后的list为：\n");
                    PrintList(La);
                } else{
                    printf("删除失败\n");
                }
                break;
            }
            case 3:{
                printf("请输入要查找的元素：\n");
                scanf("%d",&find_elem);
                if (int i=LocateElem(La,find_elem)){
                    printf("查找成功，位置为：%d\n",i);
                } else{
                    printf("查找失败\n");
                }
                break;
            }
            case 4:{
                qsort(La.elem,La.len,sizeof(int),comp);
                qsort(Lb.elem,Lb.len,sizeof(int),comp);
                printf("排序完成\n");
                PrintList(La);
                PrintList(Lb);
                break;
            }
            case 5:{
                qsort(La.elem,La.len,sizeof(int),comp);
                qsort(Lb.elem,Lb.len,sizeof(int),comp);
                printf("排序完成\n");
                SqList *pL=MergeList(La,Lb);
                printf("合并完成，list为：\n");
                PrintList(*pL);
                break;
            }
            case 6:{
                if (IntersectionElem(La,Lb)){
                    printf("\n");
                } else{
                    printf("无交集元素\n");
                }
                break;
            }
            case 0:{
                exit(0);
            }
            default:{
                printf("无此操作\n");
                break;
            }
        }
    }while (oper != 0);
    return 0;
}

Before-2
- 头插法创建链表
- 尾插法创建链表
- 链表合并

#include <iostream>

using namespace std;

typedef struct node{
    int data;
    node *next;
}*LinkList;

typedef struct DuList{
    int data;
    DuList *prior;
    DuList *next;
}*DLinkList;

void CreatDuList(DLinkList &L,int n){
    DLinkList p,q;
    L = new (DuList);
    L->next = NULL;
    L->prior = NULL;
    q = L;
    for (int i = 0; i < n; ++i) {
        p = *new (DLinkList);
        p->data = rand()%100;
        p->prior = q;
        q->next = p;
        q = p;
    }
}

void PrintDuList1(DLinkList L){
    DLinkList p = L;
    while (p != L){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}

void PrintDuList2(DLinkList L){
    DLinkList p = L;
    while (p != L){
        cout<<p->data<<" ";
        p = p->prior;
    }
    cout<<endl;
}

void DuInsert(DLinkList &L,int i){
    int cnt = 0;
    DLinkList p,q;
    q = L;
    p = (DLinkList) malloc(sizeof(DLinkList));
    while (q&&(cnt<i)){
        q = q->next;
        cnt++;
    }
    p->prior = q->prior;
    q->prior->next = p;
    q->prior = p;
    p->next = q;
}

void CreatListHead(LinkList &L,int n){
    LinkList p;
    L = new (node);
    L->next = NULL;
    for (int i = 0; i < n; ++i) {
        p = (LinkList) malloc(sizeof(node));
        p->data = rand()%100;
        p->next = L->next;
        L->next = p;
    }
}

void CreatListTail(LinkList &L,int n){
    LinkList p,q;
    L = new (node);
    q =L;
    for (int i = 0; i < n; ++i) {
        p = new (node);
        p->data = rand()%100;
        q->next = p;
        q = p;
    }
    q->next =NULL;
}

void Insert(LinkList &L,int i,int e){
    int cnt=0;
    LinkList p,q;
    p = L;
    q = new (node);
    while (p&&(cnt < i-1)){
        cnt++;
        p = p->next;
    }
    q->next = p->next;
    q->data = e;
    p->next = q;
}

void Delet(LinkList &L,int i){
    int cnt=0;
    LinkList p;
    p = L;
    while (p&&(cnt < i-1)){
        cnt++;
        p = p->next;
    }
    p->next = (*(p->next)).next;
}

void PrintList(LinkList L){
    int sum=0;
    for (LinkList p=L->next;p != NULL;p = p->next){
        cout<<p->data<<" ";

        sum++;
    }
    cout<<endl<<sum<<endl;
}

void MergeList(LinkList &L1,LinkList &L2,LinkList &L3){
    int i=0;
    LinkList p1,p2;
    L3 = new (node);
    p1 = L1;p2 = L2;
    while (p1&&p2){
        if (p1->data < p2->data) {
            Insert(L3, i, p1->data);
            p1 = p1->next;
        } else {
            Insert(L3, i, p2->data);
            p2 = p2->next;
        }
        i++;
    }
}

int main()
{
    int n;
    LinkList L1,L2,L3;
    L3 = new (node);
    cin>>n;
    CreatListHead(L1,n);
//    CreatListTail(L2,n);
    PrintList(L1);
    CreatListTail(L2,n);
    PrintList(L2);
    Insert(L1,2,3);
    PrintList(L1);
    Delet(L1,2);
    PrintList(L1);
    PrintList(L3);
    MergeList(L1,L2,L3);
    PrintList(L3);
//    int n;
//    cin>>n;
//    DLinkList L1,L2;
//    CreatDuList(L1,n);
//    PrintDuList1(L1);
//    PrintDuList2(L1);
}

10.2上机作业：

#include <iostream>

using namespace std;

typedef struct node         //单链表
{
    int data;
    struct node *next;
} *NodeList;

typedef struct SqList {     //顺序表
    int *elem;
    int len;
    int size;
};


NodeList *createEnd(NodeList &head,int len)         //单链表创立尾插法
{
    head = (node *)malloc(sizeof(NodeList));
    head->next = NULL;
    NodeList end = head;
    for (int i = 0; i < len; i++) {
        NodeList p = (NodeList)malloc(sizeof(node));
        p->data= rand()%100;
        end->next = p;
        end = p;
    }
    end->next = NULL;
}

void Print(NodeList head)                   //单链表输出
{
    int i = 0;
    if (head == NULL)
        return;
    NodeList p = head->next;
    while (p != NULL) {
        printf("%4d",p->data);
        p = p->next;
        if ((i+1)%5 == 0){
            cout<<endl;
        }
        i++;
    }
    cout<<endl;
}

void DeletElem(NodeList &head,SqList &T)        //单链表删除
{
    int i = 0,j = 0;
    NodeList p,q,temp;
    NodeList s = head;
    T.size = 1000;
    T.elem = (int*)malloc(T.size * sizeof(int));
    T.len = 0;
    p = s->next;
    while(p != NULL)
    {
        q = p;
        while(q->next != NULL)
        {
            if(q->next->data == p->data)
            {
                temp = q->next;
                q->next = q->next->next;
                T.elem[T.len++] = p->data+(i+j+1)*100;
                free(temp);
            }
            q = q->next;
            j++;
        }
        j = 0;
        i++;
        p = p->next;
    }
}

void CreatList(SqList &L,int n){            //顺序表创建
    L.elem  = (int*)malloc(n*sizeof(int));
    for (int i = 0; i < n; ++i) {
        L.elem[i] = rand()%100;
    }
    L.len = n;
}

void PrintList(SqList L){                   //顺序表输出
    for (int i = 0; i < L.len; ++i) {
        printf("%4d",L.elem[i]);
        if ((i+1)%5 == 0){
            cout<<endl;
        }
    }
    cout<<endl;
}

void DeletElem(SqList &L,SqList &T){        //顺序表删除
    T.len = 0;
    T.elem = (int *)malloc(L.len * sizeof(int ));
    for (int i = 0; i <L.len; ++i) {
        for (int j = i+1; j < L.len; ++j) {
            if (L.elem[j] == L.elem[i]){
                for (int k = j; k < L.len - 1; ++k) {
                    L.elem[k] = L.elem[k+1];
                }
                T.elem[T.len++] = L.elem[i]+j*100;
                L.len--;
            }
        }
    }
}

void ReverseLink(NodeList &Head)          //单链表倒置
{
    int flag=0;
    if (Head == NULL)
    {
        return;
    }
    NodeList pNode = Head->next;
    NodeList Prev = NULL;
    NodeList pNext = NULL;
    while (pNode != NULL){
        pNext = pNode->next;
        if (pNext == NULL){
            Head = pNode;
        }

        pNode->next = Prev;
        Prev = pNode;
        pNode = pNext;

    }
    NodeList p = (NodeList)malloc(sizeof(int));
    p->next = Head;
    Head = p;
}

int main()
{
    int n,*a;
    SqList T;
    cin>>n;
    //TODO:删除顺序表中的重复元素
    SqList L;
    CreatList(L,n);
    cout<<"顺序表创建完成:"<<endl;
    PrintList(L);
    DeletElem(L,T);
    cout<<"顺序表删除完成:"<<endl;
    PrintList(L);
    if (T.len != 0){
        cout<<"删除的元素为:"<<endl;
        for (int i = 0; i < T.len; ++i) {
            cout<<"原位置为:"<<T.elem[i]/100+1<<"->"<<T.elem[i]%100<<" ";
            cout<<endl;
        }
    } else{
        cout<<"无重复元素"<<endl;
    }
    //TODO:删除链表中的重复元素
    NodeList head;
    createEnd(head,n);
    cout<<"单链表创建完成:"<<endl;
    Print(head);
    DeletElem(head,T);
    cout<<"单链表删除完成:"<<endl;
    Print(head);
    if (T.len != 0){
        cout<<"删除的元素为:"<<endl;
        for (int i = 0; i < T.len; ++i) {
            cout<<"原位置为:"<<T.elem[i]/100+1<<"->"<<T.elem[i]%100<<" ";
            cout<<endl;
        }
    } else{
        cout<<"无重复元素"<<endl;
    }
    //TODO:单链表的逆置
    ReverseLink(head);
    cout<<"单链表逆置完成:"<<endl;
    Print(head);
}

- 顺序表中删除重复元素
- 单链表中删除重复元素
单链表的逆置