线性表的顺序和链式实现

链式实现"/>

线性表的顺序和链式实现

线性表的顺序实现基于数组完成，比较简单。

#include<iostream>
#define MaxLen 100
using namespace std;
typedef int elementType;
struct sList
{elementType data[MaxLen];int listLen;
};void initialList(sList*L)
{L->listLen = 0;
}
int listLength(sList L)
{return L.listLen;
}
elementType getElement(sList L, int i)//按位置查找元素
{if (i == 0 || i > L.listLen)cout << "error" << endl;elsereturn L.data[i - 1];return 0;
}
elementType listLocate(sList L, elementType x)//按值查找
{for (int i = 0; i < L.listLen; i++){if (L.data[i] == x)return i + 1;}return 0;
}
int listInsert(sList *L, elementType x, int i)//插入元素到指定位置。更改线性表需要引用
{if (L->listLen == MaxLen)//这里使用指针变量格式return 0;else{for (int j = L->listLen; j >= i; j--)//插入项之后的元素后移L->data[j] = L->data[j - 1];L->data[i - 1] = x;//插入L->listLen++;//表长加加return 1;}
}
int listDelete(sList* L,int i)
{if (L->listLen == 0||i>L->listLen||i<0)return 0;else{for (int j = i; j <=  L->listLen - 1; j++)L->data[j - 1] = L->data[j];L->listLen--;return 1;}
}
void listshow(sList L)
{for (int i = 0; i < L.listLen; i++)cout << L.data[i] << " ";cout << endl;
}
int main()
{sList L1;initialList(&L1);listInsert(&L1, 5, 1);listshow(L1);sList*L2=new sList;initialList(L2);listInsert(L2, 12, 1);listshow(*L2);	return 0;
}

这里，如果是指针型，则使用L->data[i],引用型则使用L.data[i];

在最后，是指针型结构体和普通结构体的区别。值得一提的是，使用指针必须使用

sLIst*L=new slist;

而不能使L->NULL;这样无法进行后续操作。

接下来是线性表的链式实现。

#include <iostream>using namespace std;//定义单链表结点类型
typedef struct LNode
{int data; //数据域struct LNode* next; //指向下一个结点的指针域
}LNode, * LinkList;//创建长度为n的单链表（顺序表）
LinkList InitList(int n)
{LinkList L;L = new LNode; //创建头结点L->next = NULL; //将头结点的指针域初始化为NULLfor (int i = n; i >= 1; i--) //逆序创建链表结点，保证顺序表元素的顺序{LNode* p; //定义一个结点指针p = new LNode; //为新结点分配地址p->data = i; //为新结点的数据域赋值p->next = L->next; //新结点的指针域指向头结点的下一个结点L->next = p; //头结点的指针域指向当前新结点}return L;
}//获取顺序表元素的操作
int GetElem(LinkList L, int i, int& e) //在单链表L中找到第i个元素，并将其赋值给e
{LNode* p; //定义一个结点指针p = L->next; //指向链表的第一个结点int j = 1; //j为计数器，查找当前结点的位置while (p && j < i) //当前结点存在且未查找到第i个元素时{p = p->next; //指向下一个结点j++; //计数器加1}if (!p || j > i) //未查找到第i个元素return 0;e = p->data; //将当前结点的数据域赋值给ereturn 1;
}//插入顺序表元素的操作
int ListInsert(LinkList& L, int i, int e) //将新结点插入到单链表L的第i个位置
{LNode* p, * s;p = L; //指向头结点int j = 0; //j为计数器，查找当前结点的位置while (p && j < i - 1) //找到要插入结点的前一个结点{p = p->next;j++;}if (!p || j > i - 1) //插入位置无效return 0;s = new LNode; //为新结点分配地址s->data = e; //将新结点的数据域赋值为es->next = p->next; //将新结点插入到当前结点之后p->next = s;return 1;
}//删除顺序表元素的操作
int ListDelete(LinkList& L, int i, int& e) //删除单链表L的第i个元素，并将其赋值给e
{LNode* p, * q;p = L; //指向头结点int j = 0; //j为计数器，查找当前结点的位置while (p->next && j < i - 1) //找到要删除的结点{p = p->next;j++;}if (!p->next || j > i - 1) //删除位置无效return 0;q = p->next; //q指向第i个结点e = q->data; //将第i个结点的数据域赋值给ep->next = q->next; //将第i个结点从单链表中删除delete q; //释放空间return 1;
}
//打印顺序表元素的操作
void PrintList(LinkList L)
{if (L->next == NULL) //如果单链表为空cout << "empty!" << endl;else{LNode* p = L->next; //指向第一个结点while (p != NULL) //当p不为空时{cout << p->data << " "; //输出当前结点的数据域p = p->next; //指向下一个结点}cout << endl;}
}
int main()
{LinkList L;/*    LinkList L; 是一段C/C++语言中的代码，它定义了一个名为L的指针变量，类型为LinkList。
其中，LinkList是对指向结构体类型为LNode的指针进行了重命名，具体来说，LinkList通过typedef关键字定义为：typedef struct LNode *LinkList;，表示指向LNode类型结构体的指针类型被重命名为LinkList，
因此LinkList L等同于LNode* L。
总之，这行代码定义了一个指向链表（或单链表）的头指针，并且头指针指向的是一个空链表，即该链表暂时没有节点，L为NULL。将LinkList L改为LNode L会引起程序错误。原因是：
LinkList是对指向LNode类型结构体的指针进行了重命名，因此LinkList类型的变量L可以存储一个指向LNode类型结构体的指针。这个指针变量L可以被用作链表的头指针。
而将LinkList L改为LNode L，则变量L不再是指向LNode类型结构体的指针，而是直接定义了一个LNode类型的变量。这样定义以后，LNode类型的变量L并不能像指针一样指向一个链表或其头节点，也就无法正确地操作链表。
因此，如果想要正确地操作链表，应该使用指向LNode类型结构体的指针，即使用LinkList类型的变量来作为链表的头指针。*/L = InitList(5); //创建长度为5的单链表PrintList(L); //输出单链表的所有元素int x;GetElem(L, 3, x); //获取单链表L中第3个元素，并将其赋值给xcout << "The 3th element of L is: " << x << endl;ListInsert(L, 4, 10); //在单链表L的第4个位置插入元素10PrintList(L); //输出单链表的所有元素ListDelete(L, 2, x); //删除单链表L中第2个元素，并将其赋值给xPrintList(L); //输出单链表的所有元素return 0;
}

如上。

行秋，写于2023年4月12日。