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

文章目录

• • 一、顺序表
  • 二、链表

一、顺序表

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

#include 
#include 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 
using namespace std;#define ERROR 0
#define OK 1typedef int ElemType;
typedef int Status;/*链表数据结构*/
typedef struct LNode {ElemType data;      // Data Fieldstruct 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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！