? ? SqList list;
? ? InitList(list);
?
? ? int n = 10;
? ??
? ? //添加10个数字给线性表list
? ? for (int i = 0; i < 10; i++)
? ? {
? ? ? ? ListInsert(list, i+1, i+1);
? ? }
? ? //删除第5个
? ? ElemType e;
? ? ListDelete(list, 5, e);
? ? printf("删除的元素是：%d\n", e);
?
? ? //在第2个位置插入一个元素-1
? ? ListInsert(list, 2, -1);
? ??
? ? //输出线性表
? ? for (int i = 0; i < 10; i++)
? ? {
? ? ? ? printf("%d ", list.elem[i]);
? ? }
? ? //输出结果是：1 -1 2 3 4 6 7 8 9 10
?
? ? system("pause");
}
二、线性链表
为了描述线性链表，我们首先要声明一个结构，如下：
?
typedef struct LNode{
? ? ElemType data; //数据域
? ? struct LNode *next;//指针域
}LNode;
定义好线性链表后，就可以对它进行操作了，常见的线性链表的基本操作有：查找、插入、删除、清空等。
线性表的基本操作在线性链表中的实现：
1.1创建链表(头插法) 时间复杂度O(n)
?
LNode * CreateListHead(int n)
{
? ? LNode *L;
? ? L = (LNode *)malloc(sizeof(LNode));
? ? L->next = NULL;
? ? LNode *p;//p为新结点，指向最后一个元素
? ? for (int i = n; i > 0; --i)
? ? {
? ? ? ? p = (LNode *)malloc(sizeof(LNode));//为新结点开辟空间
? ? ? ? scanf("%d",&p->data);
? ? ? ? p->next = L->next;
? ? ? ? L->next = p;
? ? }
? ? return L;
}
1.2创建链表(尾插法)
?
LNode * CreateListTail()
{
? ? LNode *L;
? ? L = (LNode *)malloc(sizeof(LNode));
? ? L->next = NULL;//空表
? ? LNode *s, *r = L;//r是尾指针 s是新结点
? ? int x;
? ? scanf("%d", &x);
? ? int flag = 0;//结束标记
? ? while (x != flag)
? ? {
? ? ? ? s = (LNode *)malloc(sizeof(LNode));
? ? ? ? s->data = x;
? ? ? ? r->next = s;
? ? ? ? r = s;
? ? ? ? scanf("%d", &x);
? ? }
? ? r->next = NULL;//最后一个元素next域指向NULL
? ? return L;
}
2.查找元素(取第i个元素)
?
int GetElem(LNode L, int i, ElemType &e)
{
? ? LNode *head,*p;//head是头指针，p为查找下标
? ? head = &L;
? ? p = head;//p的初值指向第1个元素
? ? int j = 0;
? ? while (p !=NULL && j
? ? {
? ? ? ? p = p->next;
? ? ? ? j++;
? ? }
? ? if (p == NULL || j>i) return -1; //第i个元素不存在
? ? e = p->data;
? ? return 0;
}
3.插入元素
在链表中插入结点，只需要修改指针。
若要在第i个结点之前插入元素，则首先需要找到第i-1个结点，然后修改第i-1个结点的指针。
时间复杂度O(n)
?
int ListInsert(LNode *L, int i, ElemType e)
{
? ? LNode *p;//设p为第i-1个结点
? ? //首先要找到第i-1个结点
? ? int j = 0;
? ? p = L;
? ? while (p != NULL && j < i-1)
? ? {
? ? ? ? p = p->next;
? ? ? ? j++;
? ? }
? ? //申请一个新结点
? ? LNode *s = (LNode *)malloc(sizeof(LNode));
? ? s->data = e;
?
? ? s->next = p->next; //s的直接后继指向p原来的直接后继
? ? p->next = s; //p的直接后继指向s
?
? ? return 0;
}
4.删除元素
若要删除第i个结点，则只需要修改第i-1个结点的指针指向第i+1个即可
时间复杂度O(L.length)即O(n)
?
int ListDelete(LNode *L, int i, ElemType &e)
{
? ? LNode *p,*q;//设p为第i-1个结点 q标示删除位置
? ? //首先要找到第i-1个结点
? ? int j = 0;
? ? p = L;//p为L的基地址
? ? while (p != NULL && j < i-1)
? ? {
? ? ? ? p = p->next;
? ? ? ? j++;
? ? }
? ? q = p->next;
? ? p->next = q->next;//p的next域指向p->next->next
?
? ? e = q->data;
? ? return 0;
}
测试代码如下：
?
#include
#include
int main()
{
? ? LNode *L;
? ? L = CreateListTail();//创建一个线性链表，输入0结束
? ? ListInsert(L, 1, 100);//在第1个位置插入100
? ? ElemType e;//待删除的元素
? ? ListDelete(L, 3, e);//删除第3个元素
? ? LNode *p;
? ? p = L;
? ??
? ? printf("输出线性链表：\n");
? ? while (p->next != NULL)
? ? {
? ? ? ? p = p->next;
? ? ? ? printf("%d ", p->data);
? ? }
?
? ? system("pause");
}
?笔者初学数据结构，如有不足之处，欢迎指正。