数据结构学习1——顺序表(C语言描述) - romi - 博客园
轻轻的风轻轻的梦，轻轻的晨晨昏昏，
淡淡的云淡淡的泪，淡淡的年年岁岁。
posts - 119, comments - 76, 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掉。
顺序表的操作基本上是这些，还有其他的操作用到时再学吧，顺序表就到此为止。接下来是线性表的链式表示和实现了，加油！C?ontents第1章 绪论11.1 什么是数据结构11.1.1 数据结构的定义11.1.2 学习数据结构的意义41.2 基本概念和术语51.2.1 数据与数据元素51.2.2 数据的逻辑结构与存储结构51.2.3 数据运算61.2.4 数据类型与抽象数据类型71.3 算法和算法描述语言81.4 算法分析91.4.1 算法评价91.4.2 算法性能分析与度量13本章小结18习题18第2章 线性表222.1 线性表的逻辑结构222.1.1 线性表的定义222.1.2 线性表的基本操作232.2 线性表的顺序存储及运算实现242.2.1 顺序表242.2.2 顺序表上基本运算的实现262.3 顺序表应用举例302.4 线性表的链式存储和运算实现312.4.1 单链表322.4.2 单链表基本运算的实现33
2.4.3 循环链表382.4.4 双向链表392.4.5 静态链表402.4.6 单链表应用举例412.5 顺序表和链表的比较46本章小结47习题48◆数据结构（C语言版）目 录第3章 栈和队列523.1 栈523.1.1 栈的定义及基本操作523.1.2 栈的顺序存储及操作实现533.1.3 栈的链式存储及操作实现563.2 栈的应用举例593.3 递归693.3.1 递归定义693.3.2 递归和栈的关系703.3.3 递归算法实例713.4 队列743.4.1 队...
直属事业部
扫描关注官方微博
扫描关注官方微信
版权所有(C)2014 清华大学出版社有限公司 京ICP备号 京公网安备48号数据结构C语言版 怎么才能学好啊，以前没有学过C语言和C++_百度知道
数据结构C语言版 怎么才能学好啊，以前没有学过C语言和C++
想学好数据结构C语言版 前提得把什么学好啊
提问者采纳
加油。祝你进步。这样一边学数据结构。所以即使没有C语言和C++基础，对知识的理解才能更深刻。但是你的书如果是数据结构C语言版的话，一边自己编程实现这些数据结构，也是可以学好数据结构的，尤其是结构体和指针的概念，还是得先了解一下C语言的基本语法，跟具体使用什么语言实现关系不大数据结构体现的是编程的思想
能给推荐本C语言的书籍吗？最好是那种比较好上手的
C程序设计 (第三版) 谭浩强著 谭浩强的书比较适合初学者看，通俗易懂。
提问者评价
来自团队：
其他类似问题
为您推荐：
数据结构的相关知识
其他3条回答
了解基本语法就可以了。建议先拿本C看看，其它就没了能看懂C
当然首先是要对C语言有一定的熟悉了。然后建议，把书上的例子，习题都好好自己输入一次。然后编译，跟踪执行。通常来说，将教科书上的都做一次。。就基本差不多了。
楼主如果是指一点基础都没得话 ，要学数据结构最好都是把c和c++都学一遍（一口吃不成胖子，要学好必需基础牢固），我建议买本c primer plus和c++ primer plus（这2本书有点小贵，我买的是正版 ，里面讲的都很详细，也可以买谭浩强的，一些大学都是以谭浩强的书做教科书）我一些参加工作的朋友都买了这2本书，c 中最重要的就是指针，c++中注意多态，类啊，如果你能很流畅的写一个（my）string类，memset()，memcpy(),memcmp()（这四个是基本功，想当初都是每天都要写这个的）的话，就能证明你的c/c++学的还不错，这时候你可以看数据结构了，学习树，二叉树，算法（例如，归并排序，插入排序），二叉树的实现，二分搜索，这时候你可以做一个二叉树分解一个矩阵，把矩阵按一维数组来表达这个矩阵，最后，就是容器，...
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁&&&&最适合初学者学习的数据结构书（C语言版）（1）
最适合初学者学习的数据结构书（C语言版）（1）
现在的初学者有个误区，非要学严大妈的那本数据结构，我想说，你能看懂吗，这是面向研究生的书籍，有一定的基础才能看懂的，里面的算法没有原码，分析了了。本书是面向初学者设计的，里面有详细的分析，有完整的原码，这本书已经在严大妈的书的垄断下在书店已经看不到了，希望大家好好珍惜，一起进步。
若举报审核通过，可奖励20下载分
被举报人：
举报的资源分：
请选择类型
资源无法下载
资源无法使用
标题与实际内容不符
含有危害国家安全内容
含有反动色情等内容
含广告内容
版权问题，侵犯个人或公司的版权
*详细原因：
免积分&&极速下载60元/年（1200次）
您可能还需要
开发技术下载排行}