线性表的实现及其基本操作

Love The Way You Lie 2022-11-17 05:28 178阅读 0赞

### 文章目录 ###

*   *  一、顺序表
     *  二、链表

## 一、顺序表 ##

初始化、赋值、插入、删除、输出、有序合并

#include <iostream>
    #include <string>
    
    using namespace std;
    
    typedef int ElemType;
    
    #define LIST_INIT_SIZE 100
    #define LISTINCREMENT 10
    
    /*数组定义*/
    typedef struct {
        ElemType* elem;//首地址
        int length;//当前长度
        int listsize;//容量
    }SqList;
    
    /*初始化*/
    SqList InitList_Sq(SqList& L) {
        L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
        //存储分配失败
        if (!L.elem) {
            exit(-2);
        }
        //空表
        L.length = 0;
        //初始化存储容量
        L.listsize = LIST_INIT_SIZE;
        return L;
        //cout << "初始化成功！";
    }
    
    //创建顺序表 赋值
    SqList setList_Sq(SqList& L) {
    	int length;
    	cout << "请输入此顺序表长度：";
    	cin >> length;
    	L.length = length;
    	cout << "请以此输入顺序表中元素的值：";
    	for (int i = 0; i < L.length; i++) {
    		cin >> L.elem[i];
    	}
    	return L;
    }
    
    /*插入*/
    int ListInsert_Sq(SqList& L, int i, ElemType e) {
        //插入的i不合法
        if (i<1 || i>L.length + 1) {
            return -1;
            //cout << "插入位置不合法";
        }
    
        //容量不够，增加分配
        if (L.length >= L.listsize) {
            ElemType* newbase = (ElemType*)(realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType)));
            if (!newbase) {
                exit(-2);
                //cout << "存储分配失败";
            }
    
            L.elem = newbase;//新基址
            L.listsize += LISTINCREMENT;//增加容量
    
        }
        int* q = &(L.elem[i - 1]);
        //插入位置及之后的元素向后移
        for (int* p = &(L.elem[L.length - 1]); p >= q; p--) {
            *(p + 1) = *(p);
        }
        //插入新的元素
        *q = e;
        //表长更新
        ++L.length;
        return 1;
        //cout << "插入成功";
    }
    
    /*删除*/
    int ListDelete_Sq(SqList& L, int i, ElemType& e) {
        if ((i < 1) || (i > L.length)) {
            //cout << "删除位置不合法";
            return 0;
        }
        int* p = &(L.elem[i - 1]);
        e = *p;
        int* q = L.elem + L.length - 1;
        for (++p; p < q; ++p) {
            *(p - 1) = *p;
        }
        --L.length;
        return 1;
    }
    
    //输出顺序表
    void printLisq_Sq(SqList L) {
    	for (int i = 0; i < L.length; i++) {
    		cout << L.elem[i] << " ";
    	}
    }
    
    /*顺序表的合并*/
    void MergeList_Sq(SqList La, SqList Lb, SqList& Lc)
    {
        ElemType* pa = La.elem;
        ElemType* pb = Lb.elem;
        Lc.listsize = Lc.length = La.length + Lb.length;
        ElemType* pc = Lc.elem = (ElemType*)malloc(Lc.listsize * sizeof(ElemType));
        if (!Lc.elem) exit(OVERFLOW);
        ElemType* pa_last = La.elem + La.length - 1;
        ElemType* pb_last = Lb.elem + Lb.length - 1;
        while ((pa <= pa_last) && (pb <= pb_last))
        {
            if (*pa <= *pb) *pc++ = *pa++;
            else *pc++ = *pb++;
        }
        while (pa <= pa_last) *pc++ = *pa++;
        while (pb <= pb_last) *pc++ = *pb++;
    }
    
    
    int main()
    {
        SqList  l;
        l = InitList_Sq(l);
        ElemType e1, e2;
        cout << "原始顺序表为：";
        printList(l);
        cout << "请输入要添加的元素的值：" << endl;
        cin >> e1;
        int i, j;
        cout << "请输入要添加的元素的位置：" << endl;
        cin >> i;
        if (ListInsert_Sq(l, i, e1)) {
            cout << "插入成功！" << endl;
            cout << "新的顺序表为：" << endl;
            printList(l);
        }
        cout << "请输入你要删除的元素的位置:" << endl;
        cin >> e2;
        cout << "请输入你要删除的元素的值：" << endl;
        cin >> j;
        if (ListDelete_Sq(l, j, e2)) {
            cout << "删除成功！" << endl;
            cout << "新的顺序表为：" << endl;
            printList(l);
        }
        
        /*顺序表的合并*/
        SqList la, lb, lc;
        la = setList_Sq(la);
        lb = setList_Sq(lb);
        MergeList_Sq(la, lb, lc);
        printLisq_Sq(lc);
        
        
    
        return 0;
    
    }

## 二、链表 ##

#include <iostream>
    using namespace std;
    
    #define ERROR 0
    #define OK 1
    
    typedef int ElemType;
    typedef int Status;
    
    /*链表数据结构*/
    typedef struct LNode {
        ElemType data;      // Data Field
        struct LNode* next; // Pointer (Link) Field
    }LNode, * LinkList;
    
    /*创建*/
    LinkList CreatList_L(int n) //尾插法
    {
        LinkList L, r, p;
        r = L = (LinkList)malloc(sizeof(LNode));
        for (int i = 1; i <= n; i++)
        {
            p = (LinkList)malloc(sizeof(LNode));
            cout << "请输入链表第" << i << "个元素的值：" << endl;
            cin >> p->data;
            r->next = p;
            r = p;
        }
        r->next = NULL;
        return L;
    }
    /*增 插入*/
    Status ListInsert_L(LinkList& L, int i, ElemType e)
    { //在带头结点单链表第 i 个结点前插入新元素x 
        LinkList p = L;
        int j = 0;
        while (p && j < i - 1)
        {
            p = p->next;
            j++;
        } //找第 i-1个结点
        if (!p || j > i - 1)
            return ERROR;
        LinkList s = (LinkList)malloc(sizeof(LNode));
        //创建新结点,其数据为x 
        s->data = e;
        s->next = p->next;
        p->next = s;
        return OK;
    }
    /*删*/
    Status ListDelete_L(LinkList& L, int i, ElemType& e)
    { //在单链表中删除第 i 个结点
        LinkList p = L;
        int j = 0;
        while (p->next && j < i - 1)
        {
            p = p->next; ++j;
        } //找第 i-1 个结点
        if (!(p->next) || j > i - 1)
            return ERROR;
        LinkList q = p->next;
        p->next = q->next; //重新链接
        e = q->data;
        free(q); //释放q结点
        return OK;
    }
    
    /*改*/
    
    /*查*/
    int LocateElem_L(LinkList L, ElemType e)
    /*在单链表L中查找值为x的结点，找到后返回其指针，否
    则返回空*/
    {
        int i = 0;
        LinkList p;
        p = L->next;
        while (p != NULL && p->data != e)
        {
            p = p->next; // 向后查找
            i++;
        }
           
        return  i + 1;
    }
    
    /*输出链表*/
    void put(LinkList L) {
    
        while (L->next!=NULL)
        {
            cout << L->next->data;
            L = L->next;
        }
        cout << endl;
    
    }
    
    int main()
    {
        
        int n;
        cout << "输入要建立的链表中元素的个数：";
        cin >> n;
        cout << endl;
    
        LinkList L = CreatList_L(n);
        cout << "新建的链表如下： " ;
         put(L);
    
         
         int choose = 1;
         while (choose)
         {     
             cout << "=================================" << endl;
             cout << "|             1.查找             |" << endl;
             cout << "|             2.删除             |" << endl;
             cout << "|             3.插入             |" << endl;
             cout << "|             0.退出             |" << endl;
             cout << "=================================" << endl;
             
             cout << "请输入你的选择：";
             cin >> choose;
    
             switch (choose)
             {
             case 1:
                 ElemType e;
                 cout << "请输入要查找的元素的值为：";
                 cin >> e;
                 cout << "所查找元素的位置为： " << LocateElem_L(L, e) << endl;
                 break;
             case 2:
                 int i;
                 cout << "请输入要删除的元素的位置： ";
                 cin >> i;
                 ElemType e2;
                 cout << "请输入要删除的元素的值： ";
                 cin >> e2;
                 if (ListDelete_L(L, i, e2)) {
                     cout << "删除成功！" << endl;
                     cout << "链表更新为：";
                     put(L);
                 }
                 else
                 {
                     cout << "删除失败！" << endl;
                 };
                 break;
             case 3:
                 int i3;
                 cout << "请输入要插入的位置：";
                 cin >> i3;
                 int e3;
                 cout << "请输入要插入的元素的值：";
                 cin >> e3;
                 if (ListInsert_L(L, i3, e3)) {
                     cout << "插入成功！" << endl;
                 }
                 else {
                     cout << "插入失败！" << endl;
                 }
                 cout << "链表更新为：";
                 put(L);
                 break;
             case 0:
                 break;
             }
    
    
         }
    
        return 0;
    }