《数据结构》复习之线性表（顺序表和链表）
1.线性表的概念
　　线性表的存储结构有顺序存储结构和链式存储结构两种。前者成为顺序表，后者称为链表。
顺序表：顺序表就是把线性表中的所有元素按照其逻辑顺序，一次存储到从指定的存储 位置开始的一块连续的存储空间中，如下图所示。
在链表的存储中，每一个节点不仅包含所存元素本身的信息，还包含元素之间的逻辑关系的信息，即前驱节点包含后继节点的地址信息，这样就可以通过前驱节点中的地址信息方便地找到后继节点的位置，如下图所示。
本文中以单链表为例。
2.线性表的比较
　　顺序表和链表各自有各自的优点和缺点，可以用下表表示：
插入删除时移动元素的个数
需要移动近一半的元素
不需要移动元素，只需修改指针
　　由此可见，当需要随机存取的时候，适合使用顺序表；当需要做频繁插入删除操作时，适合使用链表。
3.线性表的数据结构
typedef struct
T data[maxSize];
　　结构体中包括一个存储表元素数组data[]和指示元素个数的变量length。（其实顺序表就是数组）。
单链表的节点定义：
struct Node
4.顺序表的算法操作
顺序表的算法操作：
下面是我写的比较中重要的顺序表的算法操作。
#define maxSize 1000
//注意模板必须用class
class Sqlist
T data[maxSize];
length = 0;
Sqlist(T *A,int size)
for (int i = 0; i &i++)
data[i] = A[i];
T at(int loc);
//loc为数组中位置，以0开始
void insert(int loc, T value);
void display();
void push_back(T);
T erase(int loc);
//loc为数组中位置，以0开始
T Sqlist::erase(int loc)
int i = 0;
T x = data[loc];
for (i = i & i++)
//对于临界点的数，可以试着把临界点带进去
data[i] = data[i + 1];
void Sqlist::insert(int loc, T value)
//for (int i = i &i++)
//这样写是有问题的
data[i + 1] = data[i];
//所有均向后移动
int i = 0;
for (i = length-1; i &=i--)
//对于临界点的数，可以试着把临界点带进去
data[i + 1] = data[i];
data[loc] =
//不要写成i
void Sqlist::push_back(T value)
data[length] =
void Sqlist::display()
for (int i = 0; i &i++)
cout && data[i] && & &;
T Sqlist::at(int loc)
return data[loc];
int main()
int A[] = { 1, 2, 3, 4, 6, 7, 8, 9, 10 };
Sqlist ve(A, 9);
ve.push_back(11);
ve.display();
//1 2 3 4 6 7 8 9 10 11
ve.insert(4, 5);
ve.display();
//1 2 3 4 5 6 7 8 9 10 11
ve.erase(2);
ve.display();
//1 2 4 5 6 7 8 9 10 11
// char A[] = { 'a', 'b', 'c', 'e', 'f','g', 'h' };
// Sqlist ve(A, 7);
// ve.push_back('i');
// ve.display();
//a b c e f g h i
// ve.insert(3, 'd');
// ve.display();
//a b c d e f g h i
// ve.erase(2);
// ve.display();
//a b d e f g h i
　　顺序表中比较难的是插入（insert）和删除（erase）操作。再插入的过程中，要注意从最后一个元素开始至插入位置的元素，每一个元素向后移动一个单位，而不能从插入位置的元素向后移，因为这样后面的元素将被覆盖。而在删除操作时，需要从删除元素的后一个元素开始往前面移动一个单位一直移动到最后一个元素。
下面是我写的单链表的操作。
struct Node
class MyList
struct Node *
list = new struct Node;
list-&next = NULL;
void CreateListR(T a[], int n);
void CreateListF(T a[], int n);
void display();
void insert(int loc, T x);
//插入操作
int erase(T x);
//删除操作
void inverse();
//逆置操作
void inversePrint();
//逆序打印
void recurPrint(struct Node* p);
///递归操作
void MyList::inversePrint()
recurPrint(list-&next);
void MyList::recurPrint(struct Node* p)
if (p!=NULL)
recurPrint(p-&next);
cout && p-&value && & &;
void MyList::inverse()
struct Node *p = list-&
list-&next = NULL;
struct Node *q;
while (p != NULL)
q-&next = list-& //头插法
list-&next =
int MyList::erase(T x)
//struct Node *p = list-&
//struct Node *q =
//删除的时候要知道删除节点的前一个节点
//while (p != NULL)
if (p-&value==x)
//if (p == NULL)
return -1;//没有这样的节点无法删除
//q-&next = p-&
//删除操作
//return 1;
//另一种方法
struct Node *p =
while (p-&next != NULL)
if (p-&next-&value == x)
if (p == NULL)
return -1;
struct Node *tmp = p-&
p-&next = p-&next-&
void MyList::insert(int loc, T x)
struct Node *p =
//注意插入的时候要找到插入节点的前一个节点
while (loc--)
//找到对应的位置
struct Node* tmp = new struct Node;
tmp-&value =
//插入操作
tmp-&next = p-&
//可以发现插入操作和头插法很像，其实头插法就是在头结点后面插入(邪恶了)。
void MyList::display()
struct Node *p = list-&
while (p != NULL)
cout && p-&value && & &;
//不要忘记向后走
void MyList::CreateListF(T a[], int n) //头插法
struct Node* p =
for (int i = 0; i & i++)
struct Node* tmp = new struct Node;
tmp-&value = a[i];
tmp-&next = p-&
若没有头结点则为
tmp-&next =
void MyList::CreateListR(T a[], int n)
struct Node* p =
for (int i = 0; i & i++)
struct Node* tmp = new struct Node;
tmp-&value = a[i];
tmp-&next = NULL;
//尾插法要保证有一个指针永远指向最后一个节点
p-&next = NULL; //或许冗余
int main()
int A[5] = { 1, 2, 3, 4, 5 };
MyList mylist1;
mylist1.CreateListF(A, 5);
mylist1.display();
//5 4 3 2 1
cout && &************************& &&
MyList mylist2;
mylist2.CreateListR(A, 5);
mylist2.display();
//1 2 3 4 5
mylist2.insert(2, 10);
mylist2.display();
//1 2 10 3 4 5
mylist2.erase(4);
mylist2.display();
//1 2 10 3 5
mylist2.inverse();
mylist2.display();
// 5 3 10 2 1
mylist2.inversePrint();
//1 2 10 3 5
　　这里写了两种创建链表的方法，头插法（CreateListF）和尾插法（CreateListR）。头插法是在头结点后面不断插入结点，因此头插法的实现与链表元素的插入相似tmp-&next = p-& p-&next =。且头插法最后得到的链表元素顺序与插入元素顺序相反（逆置的时候可以用头插法）。尾插法需要有一个指针一直指向最后一个元素，每次在链表末尾插入元素p-&next = p = p-&。
　　此外链表比较重要的操作时插入（insert）和删除（erase）。两者的共同点是都要找到所需位置的前一个元素（插入要找到插入元素的前一个元素，删除要找到删除元素之前的元素），因此可以找一个临时指针进行跟踪。
　　插入的代码（s为插入的节点，p为插入位置之前的元素）是：s-&next=p-& p-&next=s;（可以发现头插法和这个是一样的，因为都是插入操作，注意两句语句顺序不能颠倒）。示意图如下。
　　删除也比较简单。要将单链表的第i个结点删去，必须先在单链表中找到第i-1个结点。假设p为删除节点的前一个节点。则删除代码是q=p-& p-&next=p-&next-& free(p); 。 示意图如下：
　　这边我还写如何把链表逆置（inverse头插法）和将链表元素倒着输出（inversePrint利用递归）。
5.双链表的补充
　　补充一下双链表的插入节点和删除节点算法。
　　双链表节点的数据结构如下：
struct Node
　　假设在双链表中p所指的节点之后插入一个节点s，其操作语句如下：
s-&next=p-&
s-&prior=p;
p-&next=s;
s-&next-&prior=s;
　　其特点是，先将要插入的结点的两边链接好，这样就可以保证不会发生链断之后找不到阶段的情况。
　　设要删除双链表中p结点的后继结点。其操作语句如下：
p-&next=q-&
q-&next-&prior=p;
　　顺序表对应于数组，因此并不是特别难。由于大一时观念的灌输，总觉得链表较难，但现在发现其实并不是如此，最重要的是相信自己克服恐惧大胆的写。若遇到较难的题目，可以借助画图来帮助理解。也要勇于设置相应的辅助指针。//顺序表的各种操作（包括头删，尾删，插入，逆序，摧毁，清空等等）
#ifndef _SEQLIST_H
#define _SEQLIST_H
#include&stdio.h&
typedef int ElemT
#define INIT_SIZE
typedef struct SeqList
ElemType *
int isempty(SeqList *list);
int isfull(SeqList *list);
void InitList(SeqList *list);
void push_back(SeqList *list, ElemType x);
void show_list(SeqList *list);
void push_front(SeqList *list, ElemType x);
void pop_back(SeqList *list);
void pop_front(SeqList *list);
void insert_pos(SeqList *list, ElemType x, int pos);
void quit_system(SeqList *list, int *x);
int find(SeqList *list, ElemType x);
int length(SeqList *list);
void insert_val(SeqList *list, ElemType x);
void sort(SeqList *list);
void delete_pos(SeqList *list,int pos);
void delete_val(SeqList *list, ElemType x);
void clear(SeqList *list);
void destory(SeqList *list);
void reverse(SeqList *list);
//函数文件
#include"SeqList.h"
int isempty(SeqList *list)
//检测表是否满
return list-&size == 0;
int isfull(SeqList *list)
//检测表是否空
return list-&size &= list-&
void InitList(SeqList *list)
//表初始化
list-&capacity = INIT_SIZE;
list-&base = (ElemType *)malloc(sizeof(ElemType)*list-&capacity);
list-&size = 0;
void push_back(SeqList *list, ElemType x)
if (isfull(list))
printf("顺序表已满,不能插入!\n") ;
list-&base[list-&size] =
list-&size++;
void show_list(SeqList *list)
if (list-&size == 0)
printf("顺序表为空。\n");
for (i = 0; i&list-& ++i)
printf("%d ", list-&base[i]);
printf("\n");
void push_front(SeqList *list, ElemType x)
if (isfull(list))
printf("顺序表已满,不能插入!\n");
for (i = list-& i & 0; i--)
list-&base[i] = list-&base[i - 1];
list-&base[0] =
(list-&size)++;
void pop_front(SeqList *list)
if (isempty(list))
printf("顺序表为空，不能删除\n");
for (i = 0; i & list-& i++)
list-&base[i] = list-&base[i + 1];
(list-&size)--;
void pop_back(SeqList *list)
if (isempty(list))
printf("顺序表为空，不能删除\n");
list-&size--;
void insert_pos(SeqList *list, ElemType x, int pos)
////按位置插
if (pos&0 || pos&list-&size)
printf("插入的位置不正确。\n ");
if (isempty(list))
printf("顺序表已满，不能插入.\n");
for (i = list-& i & i--)
list-&base[i] = list-&base[i - 1];
list-&base[pos] =
list-&size++;
void quit_system(SeqList *list, int *x)
int find(SeqList *list, ElemType x)
for (i = 0; i & list-& i++)
if (list-&base[i]==x)
return -1;
int length(SeqList *list)
return list-&
void insert_val(SeqList *list, ElemType x)
//按值插入
push_back(list, x);
sort(list);
void sort(SeqList *list)
if (isempty(list))
for (int i = 1; i & list-& i++)
for (int j = 0; j & list-&size - j++)
if (list-&base[j]&list-&base[j + 1])
temp = list-&base[j];
list-&base[j] = list-&base[j + 1];
list-&base[j + 1] =
void delete_pos(SeqList *list, int pos)
//按位置删除
if (isempty(list))
printf( "顺序表为空，不能删除。\n" );
if (pos & 0 || pos &= list-&size)
printf("删除的位置不正确。\n");
for (int i = i & list-& ++i)
list-&base[i] = list-&base[i + 1];
list-&size--;
void delete_val(SeqList *list, ElemType x)
//按值删除
if (isempty(list))
printf( "顺序表为空，不能删除。\n");
int pos = find(list,x);
if (pos == -1)
printf("未找到该数。\n");
delete_pos(list,pos);
void clear(SeqList *list)
list-&size = 0;
void destory(SeqList *list)
list-&base = NULL;
void reverse(SeqList *list)
for (int i = 0, j = list-&size - 1; i & list-&size / 2; i++, j--)
int temp = list-&base[i];
list-&base[i] = list-&base[j];
list-&base[j] =
#include"SeqList.h"
void main()
InitList(&mylist);
int select = 1;
ElemType I
while (select)
printf("****************************************************\n");
[1] show_list
[2] quit_system
[3] push_front
[4] push_back
[5] pop_front
[6] pop_back
[7] insert_pos
[8] insert_val
[9] delete_pos
[10] delete_val
[12] length
[13] clear
[14] destory
[15] reverse(逆序)
[16] sort(顺序)
printf("****************************************************\n");
printf("请选择:");
scanf_s("%d", &select);
switch (select)
show_list(&mylist);
quit_system(&mylist, &select);
printf("请输入要插入的值(-1结束):&");
while (scanf_s("%d", &Item), Item != -1)
push_front(&mylist, Item);
printf("请输入要插入的值(-1结束):&");
while (scanf_s("%d",&Item) , Item != -1)
push_back(&mylist, Item);
pop_front(&mylist);
pop_back(&mylist);
printf("请输入要插入的位置：");
scanf_s("%d", &pos);
printf("请输入要插入的值：");
scanf_s("%d", &Item);
insert_pos(&mylist, Item, pos);
printf("请输入要插入的数：");
scanf_s("%d", &Item);
insert_val(&mylist, Item);
printf("请输入要删的位置：");
scanf_s("%d",&pos);
delete_pos(&mylist,pos);
printf("请输入要删的值:");
scanf_s("%d", &Item);
delete_val(&mylist,Item);
printf("请输入要查找的数：");
scanf_s("%d", &Item);
pos=find(&mylist, Item);
if (pos != -1)
printf("该数为第%d个数.\n", pos);
printf("未找到该数。\n");
printf("该顺序表长度为：%d\n",length(&mylist));
clear(&mylist);
destory(&mylist);
reverse(&mylist);
sort(&mylist);
C语言---动态创建顺序表及定义、插入、删除操作
题目：编写一个程序，动态的创建一个顺序表。要求：顺序表的初始长度为10，向顺序表中输入15个整数，并打印出来；再删除顺序表中的第5个元素，打印出删除后的结果。程序代码：#include &lt...
数据结构之顺序表（创建、使用、销毁）
顺序表是在计算机内存中采用顺序存储的方式存储的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。顺序表的物理结构和逻辑结构都是连续的。顺序表的增删操作麻烦，需要移动的元素可能很多，修改和...
C语言数据结构实战(一)顺序表的插入与删除
C语言数据结构实战(一)顺序表的插入与删除博客分类： C语言 今天学习了思成老师的数据结构实战教程 写了一个顺序表 插入和删除的操作 把源码共享给大家 一共包括list.c stu.h main.c ...
数据结构--顺序表的建议和删除
顺序表的建立和删除
#include &stdio.h&
#include &stdlib.h&
#define OK
数据结构-顺序表（3）顺序表的建立、销毁、置空
代码 分析与思考
creat table (field type,field type..);
修改表结构：
（添加列，专业一点说就是，往表中添加新字段）
使用 DELETE 语句从表中删除数据。
DELETE [FROM]
condition];
使用WHERE 子句指定删除的记录。
记录使用jqGrid操作表格的相关方法，方便查找。。。
创建表格：
//设置功能选项
var option={
data:data,
datatype:&local&q...
====================================================================================================...
一、单链表
单链表，就是线性表的链式存储结构，又称线性链表。
它的特点是：用一组任意的存储单元存储线性表的数据元素，即结点之间在逻辑上是连续的，在物理上是不连续的。
没有更多推荐了，【c语言数据结构顺序表】 - CSDN数据结构 已知一个顺序表递增有序,试设计一种算法,将x插入到表中的适当位置,以保持顺序表的有序性-学路网-学习路上 有我相伴
数据结构 已知一个顺序表递增有序,试设计一种算法,将x插入到表中的适当位置,以保持顺序表的有序性
来源：互联网 &责任编辑：王小亮 &
数据结构上面的一个题:画出和下列已知序列对应的森林F:先序...在数据结构中,如何通过访问序列确定对应的树?例如已知树的先根次序访问序列后根次序访问序列:[左(后根次序)]-&[右(后根次序)]-&根[]表示一(数据结构)设计一个算法从顺序表中删除重复元素,并使剩余元素...题目没说明顺序表原先重复元素是否放在一起,例如4342。重复元素是4,但是你自己写的算法只能处理重复元素相邻放置的情况~设有一个线性表采用顺序存储结构,表中的数据元素值为正整数...不知道你是否学过快速排序算法,在算法中有划分算法,实现的就是你说的这个操作。思想是:以第一个元素为轴,开始时设置2个指针(一个在最左端【不包括第一个元素】,一个在...已知长度为n的线性表A采用顺序存储结构,设计一个算法,使得该...相当于数组的顺序排列数据结构(C语言)设有一个线性表E,将线性表逆置,要求逆线性表...输入数据,输出数据,及线性表的长度,询问是否查找数据,若查找则由用户输入需查找的数据,显示此数据在线性表中的位置(第几个)*/#include&stdio.h&#include&stdlib....数据结构已知一个顺序表递增有序,试设计一种算法,将x插入到表中的适当位置,以保持顺序表的有序性(图2)数据结构已知一个顺序表递增有序,试设计一种算法,将x插入到表中的适当位置,以保持顺序表的有序性(图5)数据结构已知一个顺序表递增有序,试设计一种算法,将x插入到表中的适当位置,以保持顺序表的有序性(图7)数据结构已知一个顺序表递增有序,试设计一种算法,将x插入到表中的适当位置,以保持顺序表的有序性(图9)数据结构已知一个顺序表递增有序,试设计一种算法,将x插入到表中的适当位置,以保持顺序表的有序性(图12)数据结构已知一个顺序表递增有序,试设计一种算法,将x插入到表中的适当位置,以保持顺序表的有序性(图14)这是用户提出的一个学习问题,具体问题为:数据结构 已知一个顺序表递增有序,试设计一种算法,将x插入到表中的适当位置,以保持顺序表的有序性我们通过互联网以及本网用户共同努力为此问题提供了相关答案,以便碰到此类问题的同学参考学习,请注意,我们不能保证答案的准确性,仅供参考,具体如下:数据结构(C语言)设有一个线性表E,将线性表逆置,要求逆线性表...输入数据,输出数据,及线性表的长度,询问是否查找数据,若查找则由用户输入需查找的数据,显示此数据在线性表中的位置(第几个)*/#in防抓取，学路网提供内容。用户都认为优质的答案:已知长度为n的线性表A用顺序存储结构设计一个算法,似的线性...将一个链表逆序并输出。我用了两种方法来实现,第一种是借助了一个新的空链表;第二...structNode*//指针域}Node防抓取，学路网提供内容。这相当于是一个插入排序的子程序.求一C++数据结构算法:已知线性表中的元素以值递增有序排列...//如果前后两个数据不相等,则两个指针都向后移一个节点if(currNode-&next==NU...}}时间复杂度为n,因为只要防抓取，学路网提供内容。假设数组arr已经有序,数组长度为len,现要将x插入适当位置以保持有序性.程序如下：6,已知一个顺序表A,设计一个算法删除顺序表中值为item的数据...LinkA;//顺序表A,假设A的元素类型为CTypevoidgetItem(CTypeitem){LinkB=A防抓取，学路网提供内容。int i = len - 1;求一C++数据结构算法:已知线性表中的元素以值递增有序排列...LinkNoder=//记录当前节点;LinkNodeq=NULL;//记录逆转节点的下一个节...=p;//逆转p=r;//防抓取，学路网提供内容。while (i >= 0 && arr[i] > x){
arr[i+1] = arr[i];问:【数据结构】写一个算法1.顺序存储线性表中的元素按值非...#includeintmain(){inta[20]={23,14,22,45,13,90,45,67,83,84,56,44,22,4防抓取，学路网提供内容。}arr[i+1] =我重装系统的时候，会出现：“内部安装程序数据结构...问：电脑反应慢，老是死机，所以重装系统，怎么就出现这样子了，现在电脑都...答：你的硬盘是IDE的还是SATA的，安装系统的时候最好把硬盘重新格式防抓取，学路网提供内容。有问题欢迎追问!重做系统，提示内部安装程序数据结构已损坏问：用u盘按照网上教程在台机重做系统成功，但是在笔记本上就安装失败。刚...答：你好，换个系统文件安装试试。防抓取，学路网提供内容。已知长度为n的线性表A用顺序存储结构设计一个算法,似的线性...将一个链表逆序并输出。我用了两种方法来实现,第一种是借助了一个新的空链表;第二...structNode*//指针域}Node,*ptr_NtypedefstructLinkList{//链表结构...求一C++数据结构算法:已知线性表中的元素以值递增有序排列...//如果前后两个数据不相等,则两个指针都向后移一个节点if(currNode-&next==NU...}}时间复杂度为n,因为只要顺序遍历下去就行了6,已知一个顺序表A,设计一个算法删除顺序表中值为item的数据...LinkA;//顺序表A,假设A的元素类型为CTypevoidgetItem(CTypeitem){LinkB=A;while(B-&next!=null){if(B-&Item==item){B-&next=B-&next-&n...求一C++数据结构算法:已知线性表中的元素以值递增有序排列...LinkNoder=//记录当前节点;LinkNodeq=NULL;//记录逆转节点的下一个节...=p;//逆转p=r;//下一次遍历r=q;}}//打印链表数据void...
相关信息：
- Copyright & 2017 www.xue63.com All Rights Reserved数据结构学习1——顺序表(C语言描述) - romi - 博客园
轻轻的风轻轻的梦，轻轻的晨晨昏昏，
淡淡的云淡淡的泪，淡淡的年年岁岁。
posts - 119, comments - 87, trackbacks - 0, articles - 0
数据结构本人主要学习严蔚敏老师的《数据结构(C语言版)》，本人根据自己的需要学习了书中的算法并将其代码实现还加了自己的一些学习心得体会，现将学习历程记录下来以便日后需要时参考。主要是学的东西一多，这些当时掌握了的东西长久不用又会忘，而且自己的思路都是宝贵的财富啊，弃之可惜，所以记录下来需要时随时看看，免得又拿着一本书从头开始还要到处找代码。
线性表是最常用最简单的一种数据结构，一个线性表是n个数据元素的有限序列。线性结构的顺序表示指的是用一组地址连续的存储单元一次存储线性表的数据元素，以元素在计算机内"物理位置相邻"来表示线性表中数据元素之间的逻辑关系。
数据结构的学习就从这最简单线性表中最简单的顺序表示开始。
相关概念：直接前驱元素，直接后驱元素，空表，位序等因为很简单在此不予详细介绍。
只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。由于高级程序设计语言(这里主要用指C)中的数组类型也有随即存取的特性，因此，通常用数组来描述数据结构中的顺序存储结构。
学习步骤如下：顺序表构造&&顺序表初始化&&插入元素&&删除元素&&元素比较&&两个顺序表比较。
1.顺序表构造
顺序表构造前进行如下宏定义和变量替换，方便代码的理解：
#define TRUE 1
#define FALSE 0
#define OK 1
#define ok 1
#define ERROR 0
#define error 0
#define INFEASIBLE -1
#define LIST_INIT_SIZE 100;
#define LISTINCREMENT 10;
typedef int ElemT
typedef int S
采用结构体构造一个顺序表，定义顺序表的地址、长度、存储容量的表示，代码如下：
typedef struct{
ElemType *
//定义了顺序表中元素类型的数组指针，指向顺序表存储空间的基址
//顺序表的长度(也即元素个数)
//当前分配给顺序表的存储容量
2.顺序表的初始化
接下来对该顺序表进行初始化，为顺序表分配一个预定义大小的数组空间，并将当前顺序表长度设为0，如果元素个数大于分配的存储容量则再对容量进行扩充(初始化时不扩充，顺序表使用中按需要进行容量扩充)。代码如下：
Status InitList(SqList *L)
(*L).elem=(ElemType*)malloc(100*sizeof(ElemType));
//不知什么问题不能用LIST_INIT_SIZE，必须用100，下面的realloc函数也是一样？
if((*L).elem==NULL)
exit(OVERFLOW);
(*L).length=0;
(*L).listsize=LIST_INIT_SIZE;
malloc函数的使用：
函数原型：extern void *malloc(unsigned int num_bytes)
函数作用：向系统申请分配指定size个字节的内存空间。返回类型是 void* 类型。void* 表示未确定类型的指针。C,C++规定，void* 类型可以强制转换为任何其它类型的指针
头文件：VC中利用malloc函数时要加malloc.h或stdlib.h
返回值：如果分配成功则返回指向被分配内存的指针，否则返回空指针NULL。当内存不再使用时，应使用free()函数将内存块释放。
代码中(*L).elem=(ElemType*)malloc(100*sizeof(ElemType));这句话返回值类型被强制转换为ElemType*,因为返回值指向被配分内存指针(即顺序表*L的elem元素)。分配内存大小为100个ElemType所占字节
为了调试方便，创建一个顺序表并初始化，给其指定一定长度并向表中各元素赋值，代码如下：
SqList* L1=new SqList();
InitList(L1);
//测试InitList函数
(*L1).length=10;
for(int j=0;j&(*L1).j++)
(*L1).elem[j]=j;
注意：定义了指针变量后，一定要将其初始化。一个不指向任何地址空间的指针是十分危险的！上面定义了一个SqList结构体指针变量并对其分配了内存空间。
为方便测试、简化代码量，写一个输出函数以供调用，用于输出顺序表L的个元素。代码如下：
void Output_L(SqList *L)
for(int i=0;i&(*L).i++)
cout&&(*L).elem[i]&&" ";
可以调用Output_L函数看下顺序表L1的输出情况：Output_L(L1);&& 显示结果如下：
初始化的这个顺序表L1在本文后面进行测试时会大量用到。
3.顺序表中元素的插入
功能：在顺序表第i个位置前加入新的元素e。
思路：第i个位置加入元素e，那么原来在第i个位置的元素就要移到i+1个位置中，依次向后推。移完后顺序表长度+1。关键是如何移动的问题，如果从先插人e再移动，则插入后第i个位置的值是e，原先第i个位置的值就不知道了，因为存储空间被e占用了，因此移动前还需要用个地址保存原先位置上的值。这样比较麻烦，我们采用高低址向低地址移动，先将顺序表最后一个位置(假设为p)的值传入(P+1)中，这样位置p就空出来了，将p-1的值放入p中，以此类推，最后第i个位置也空出来了，将e放入其中，这样就完成了顺序表的插入工作。
因为要插入元素，所以首先判断插入的位置是否正确，再判断存储空间够不够，不够就增加内存分配。
注意：这里我采用的是插入指针e中的值到顺序表的第i个位置，因为ListInsert这个函数还要用到后面的一些功能中，我在学习过程中调试过很多次，有的函数参数用指针，有的函数参数没用指针，在进行函数调用时很容易出错，所以呢这里统一使用指针，以免函数调用时参数出现各种不匹配，改又不好改。代码如下：
Status ListInsert(SqList (*L),int i,ElemType *e)
ElemType *newbase,*p,*q;
if(i&1||i&(*L).length+1)
return ERROR;
if((*L).length&=(*L).listsize)
newbase=(ElemType *)realloc((*L).elem,((*L).listsize+10)*sizeof(ElemType));
//不能用LISTINCREMENT，必须用10，下面一行就能用，为甚么？和realloc这个函数有关系吗
(*L).elem=
(*L).listsize=(*L).listsize+LISTINCREMENT;
q=&((*L).elem[i-1]);
for(p=&((*L).elem[(*L).length-1]);p&=q;p--)
*(p+1)=*p;
(*L).length++;
需要注意的是for循环中的循环终止条件。
realloc函数的使用:
函数原型：extern void *realloc(void *mem_address, unsigned int newsize)
参数意义：void*表示返回指针的数据类型，可以强制转换为其他类型(这点和malloc是一样的)；函数第一个参数表示要改变内存大小的指针名，即要改变的是哪个指针指向的内存；第二个参数表示要分配的新的大小，新的大小一定要大于原来的大小不然会导致数据丢失。
头文件：#include &stdlib.h& 有些编译器需要#include &alloc.h&
功能：先按照newsize指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来mem_address所指内存区域，同时返回新分配的内存区域的首地址。即重新分配存储器块的地址。
返回值：如果重新分配成功则返回指向被分配内存的指针，否则返回空指针NULL。
注意：这里原始内存中的数据还是保持不变的。当内存不再使用时，应使用free()函数将内存块释放。
下面对ListInsert这个函数进行测试，假设将指针LI2中的值插入顺序表L1中第5个位置，代码如下：
ElemType LI1=8;
ElemType *LI2;
ListInsert(L1,5,LI2);
cout&&"测试ListInsert函数:"&&
Output_L(L1);
调试结果显示如下：
4.顺序表中元素的删除
功能：将顺序表的第i个位置的元素参数，并将该元素存到指针e中
思路：删除第i个位置的元素后，后面所有的元素所在的位置都要向前移一位。与元素添加后移位的方法相反，元素删除后我们采取从地址低的位置向地址高的位置移动。因为是删除元素，所以就不必判断存储空间够不够了，但删除的位置是否靠谱还是必须要判断的。不要忘了最后顺序表的长度要-1。
代码如下：
Status ListDelete(SqList *L,int i,ElemType *e)
ElemType *p,*q;
if(i&0||i&=(*L).length)
q=&((*L).elem[i-1]);
//q为被删除元素的位置
p=&((*L).elem[(*L).length-1]);
//p指向顺序表最后一个元素位置的地址
for(q;q&p;q++)
*q=*(q+1);
(*L).length--;
需要注意的是for循环中的循环终止条件，可以和元素插入算法相比较下，有什么差别。
对ListDelete函数进行测试，假设删除的是顺序表中L1第4个位置的元素，并将元素存储到指针变量e中，代码如下：
ElemType *e=new ElemType();
cout&&"测试ListDelete函数:"&&
ListDelete(L1,4,e);
Output_L(L1);
cout&&"e="&&*e&&
调试结果显示如下：
5.顺序表中元素比较
功能：在顺序线性表中查找第一个与指针e中的值满足Compare()关系的元素的位置，返回该位置，没有就返回0。
首先，先定义一下Compare()这个函数，就假设这个关系是相等关系吧，利用Compare这个函数实现，如果两个指针中的值相等就返回true，不相等就返回false。代码如下：
bool Compare(ElemType* e1,ElemType* e2)
//参数要就都用指针表示，以免函数间相互调用时参数出现不匹配问题
if(*e1==*e2)
根据这个关系，要找出顺序表中的元素，明显的思路就是一个个元素进行对比了，看是否满足Compare()关系。这里需要注意的一点是元素的位置和数组元素的表示，第i个位置的元素是(*L).elem[i-1]。代码如下：
int LocateElem(SqList *L,ElemType *e)
//i为顺序表中的位置
ElemType *p;
//p指向顺序表中位序为i的元素
//取数组首元素地址
while(i&=(*L).length&&(!Compare(p,e)))
if(i&=(*L).length)
//返回满足条件的元素所在位置i
对LocateElem函数进行测试，代码如下：
ElemType LE1=4;
ElemType *LE2;
cout&&"测试LocateElem函数:"&&
int a=LocateElem(L1,LE2);
cout&&LE1&&"元素的位置："&&a&&
调试显示结果如下：
6.两个顺序表之间的运算
功能：将存在线性表Lb中而不存在La中的数据元素插入到线性表La中，是在La中元素后面依次插入，没有按什么顺序插入。
思路：这算是顺序表应用的小综合，首先要判断线性表Lb中的各元素在线性表La中是否存在，要用到LocateElem函数，还要对元素进行插入，要用到ListInsert函数。因为这两个函数前面都理解的很透彻了，再来完成这个算法想必会比较简单。
算法涉及到取元素，定义一个函数GetElem()将线性表L中第i个元素存入指针e中，代码如下：
void GetElem(SqList *L,int i,ElemType *e)
if(i&0&&i&=(*L).length)
*e=(*L).elem[i-1];
利用这个函数和前面的两个函数完成该算法就很简单了，直接放代码，如下：
void Collect(SqList *La,SqList *Lb)
ElemType *e=new ElemType();
//局部指针变量分配了内存空间，用完后要注意释放内存空间
int La_len=(*La).
int Lb_len=(*Lb).
for(int i=1;i&=Lb_i++)
GetElem(Lb,i,e);
if(!LocateElem(La,e))
ListInsert(La,La_len+1,e);
//注意这个时候La的长度并没有加1
delete(e);
对该算法进行测试，测试时要初始化另外一个顺序表L2，代码如下：
cout&&"测试Connect函数:"&&
SqList *L2=new SqList();
InitList(L2);
//定义了SqList变量并初始化后，在赋值之前千万别忘了使用该函数构造空一个线性表
(*L2).length=10;
for(int j=0;j&(*L2).j++)
(*L2).elem[j]=j*2;
cout&&"线性表L2："&&
Output_L(L2);
Collect(L1,L2);
cout&&"执行Connect函数后的线性表L1:"&&
Output_L(L1);
调试显示结果如下：
注意：程序最后不要忘了将用new分配了内存空间的指针变量用delete释放内存空间。顺序表如果不用了，申请的内存空间要free掉。
顺序表的操作基本上是这些，还有其他的操作用到时再学吧，顺序表就到此为止。接下来是线性表的链式表示和实现了，加油！}