实例设计
1、编程实现如下任务：建立一个线性表，首先依次输入数据元素1, 2, 3,…,10，然后删除数据元素5，最后依次显示当前线性表中的数据元素。假设该线性表的数据元素个数在最坏情况下不会超过100个。要求使用顺序表。
#include<stdio.h> #define MaxSize 100 typedef int ElemType; #include"sequencelist.h" void main(void) { SequenceList myList; //声明 int i, x; ListInitialize(&myList); //初始化 for(i = 0; i<10; i++) { ListInsert(&myList, i, i+1); //插入 } ListDelete(&myList, 4, &x); //删除5即下标为4 for(i = 0; i<ListLength(myList); i++) { ListGet(myList, i, &x); //获取 printf("%d ", x); } }
2、设计一个顺序表的删除函数，把顺序表L中的数据元素x删除。
//成功返回1，不成功返回0 int ListDeleteX(SequenceList *L, ElemType x) { int i, j; for(i=0; i<L->size; i++) { if(x == L->list[i]) { break; //找到x则退出循环 ，此时x下标已被记录 } } if(i == L->size) return 0; for(j = i; j<L->size; j++) { L->list[j] = L->list[j+1]; //向前移动一位 } L->size--; return 1; }
3、编写算法实现顺序表逆置，要求把顺序表A中数据元素序列（a0,a1,a2,…..an-1）逆置为（an-1, ….. a2, a1,a0）存储到顺序表B中。
void Converse(SequenceList la, SequenceList *lb) { int i; ListInitialize(lb); for(i = 0; i<la.size; i++) { lb->list[i] = la.list[la.size-i-1]; lb->size++; } }
4、自身逆置
void ConverseSelf(SequenceList *la) { SequenceList lb; int i, j; ListInitialize(&lb); for(i = 0; i<la->size; i++) { lb.list[i] = la->list[la->size-i-1]; lb.size++; } for(j = 0; j<lb.size; j++) { la->list[j] = lb.list[j]; } }
4 线性表的链式表示和实现
单链表中，构成链表的结点只有一个指向直接后继结点的指针域。
单链表的表示方法:
单链表存储结构
可以定义单链表结点的结构体如下：
/*线性表的单链表存储结构*/
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node *next;
} Node;
typedef struct Node *LinkList;
其中，data域用来存放数据元素，next域用来存放指向下一个结点的指针。单链表有带头结点结构和不带头结点结构两种。我们把指向单链表的指针称作头指针。头指针所指的不存放数据元素的第一个结点称作头结点。存放第一个数据元素的结点称作第一个数据元素结点。第一个数据元素结点在带头结点的单链表中是链表中的第二个结点，在不带头结点的单链表中是链表中的第一个结点。一个带头结点的单链表下图所示。
单链表空单链表空连和非空链和非空链
单链表的操作实现
1、C语言的动态申请内存空间函数
C语言提供了动态申请内存空间函数malloc()和动态释放函数内存空间的函数free()。这些函数包含在头文件malloc.h中。malloc()函数的原型是：
void malloc(unsigned size)`
malloc()函数用于向系统动态申请size个字节的内存单元空间，函数返回值为所申请内存空间的首地址。free()函数的原型是：
void free(void *p)
2、单链表的结点定义
单链表是由一个个结点链接而成的，单链表中每个结点的结构体定义如下：
typedef struct node
{ //结点类型定义
DataType data; //结点的数据域
struct node *next;//结点的指针域
}ListNode;
3、单链表的操作实现
在带头结点的单链存储结构下，线性表抽象数据类型定义的各个操作的具体实现方法如下。
单链表的创建
//初始化 int InitList(LinkList &L) { //构造一个单链表 L=new LNode; //生成头结点，用头指针L指向头结点 L->next =NULL; return 1; }
单链表的读取
在单链表中读取第i个元素，我们无法一开始知道，必须从头开始找。
typedef int DateType; /*初始条件：顺序线性表L已经存在，1<=i<=ListLength(L)*/ /*操作结果：用e返回L中第i个数据元素的值*/ int GetDate(LinkList L, int i, DateType *x) { int j; LinkList p; p = L->next; /*让指针p指向链表L的第一个节点*/ j = 1; while (p && j<i) /*p不为空且计数器j还没有等于i时，循环继续*/ { p = p->next; ++j; } if (!p || j > i) { return 0; /*第i个节点不存在*/ } *x = p->data; /*取第i个节点的数据*/ return 1; }
单链表的插入
