【数据结构C语言实现系列——线性表】#include
#include
typedef int elemType;
/************************************************************************/
/*以下是关于线性表顺序存储操作的16种算法*/
/************************************************************************/
struct List{
elemType *list;
int size;
int maxSize;
};
void againMalloc(struct List *L)
{
/* 空间扩展为原来的2倍，并由p指针所指向，原内容被自动拷贝到p所指向的存储空间 */
elemType *p = realloc(L- >list, 2 * L->maxSize * sizeof(elemType));
if(!p){/* 分配失败则退出运行 */
printf( "存储空间分配失败！ ");
exit(1);
}
L- >list = p;
/* 使list指向新线性表空间 */
L- >maxSize = 2 * L->maxSize;
/* 把线性表空间大小修改为新的长度 */
}
/* 1.初始化线性表L，即进行动态存储空间分配并置L为一个空表 */
void initList(struct List *L, int ms)
{
/* 检查ms是否有效，若无效的则退出运行 */
if(ms<= 0){
printf( "MaxSize非法！ ");
exit(1);
/* 执行此函数中止程序运行，此函数在stdlib.h中有定义 */
}
L- >maxSize = ms;
/* 设置线性表空间大小为ms */
L- >size = 0;
L- >list = malloc(ms * sizeof(elemType));
if(!L- >list){
printf( "空间分配失败！ ");
exit(1);
}
return;
}
/* 2.清除线性表L中的所有元素，释放存储空间，使之成为一个空表 */
void clearList(struct List *L)
{
if(L- >list != NULL){
free(L- >list);
L- >list = 0;
L- >size = L->maxSize = 0;
}
return;
}
/* 3.返回线性表L当前的长度，若L为空则返回０ */
int sizeList(struct List *L)
{
return L- >size;
}
/* 4.判断线性表L是否为空，若为空则返回1, 否则返回0 */
int emptyList(struct List *L)
{
if(L- >size ==0){
return 1;
}
else{
return 0;
}
}
/* 5.返回线性表L中第pos个元素的值，若pos超出范围，则停止程序运行 */
elemType getElem(struct List *L, int pos)
{
if(pos< 1 || pos > L->size){/* 若pos越界则退出运行 */
printf( "元素序号越界！ ");
exit(1);
}
return L- >list[pos - 1];
/* 返回线性表中序号为pos值的元素值 */
}
/* 6.顺序扫描（即遍历）输出线性表L中的每个元素 */
void traverseList(struct List *L)
{
int i;
for(i = 0;
i< L->size;
i++){
printf( "%d ", L ->list[i]);
}
printf( " ");
return;
}
/* 7.从线性表L中查找值与x相等的元素，若查找成功则返回其位置，否则返回-1 */
int findList(struct List *L, elemType x)
{
int i;
for(i = 0;
i< L->size;
i++){
if(L- >list[i] == x){
return i;
}
}
return -1;
}
/* 8.把线性表L中第pos个元素的值修改为x的值，若修改成功返回1，否则返回0 */
int updatePosList(struct List *L, int pos, elemType x)
{
if(pos< 1 || pos > L->size){/* 若pos越界则修改失败 */
return 0;
}
L- >list[pos - 1] = x;
return 1;
}
/* 9.向线性表L的表头插入元素x */
void inserFirstList(struct List *L, elemType x)
{
int i;
if(L- >size == L->maxSize){
againMalloc(L);
}
for(i = L- >size - 1;
i >= 0;
i--){
L- >list[i + 1] = L ->list[i];
}
L- >list[0] = x;
L- >size ++;
return;
}
/* 10.向线性表L的表尾插入元素x */
void insertLastList(struct List *L, elemType x)
{
if(L- >size == L ->maxSize){/* 重新分配更大的存储空间 */
againMalloc(L);
}
L- >list[L->size] = x;
/* 把x插入到表尾 */
L- >size++;
/* 线性表的长度增加１ */
return;
}
/* 11.向线性表L中第pos个元素位置插入元素x，若插入成功返回１，否则返回０ */
int insertPosList(struct List *L, int pos, elemType x)
{
int i;
if(pos< 1 || pos > L->size + 1){/* 若pos越界则插入失败 */
return 0;
}
if(L- >size == L->maxSize){/* 重新分配更大的存储空间 */
againMalloc(L);
}
for(i = L- >size - 1;
i >= pos - 1;
i--){
L- >list[i + 1] = L->list[i];
}
L- >list[pos - 1] = x;
L- >size++;
return 1;
}
/* 12.向有序线性表L中插入元素x, 使得插入后仍然有序*/
void insertOrderList(struct List *L, elemType x)
{
int i, j;
/* 若数组空间用完则重新分配更大的存储空间 */
if(L- >size == L->maxSize){
againMalloc(L);
}
/* 顺序查找出x的插入位置 */
for(i = 0;
i< L->size;
i++){
if(x< L->list[i]){
break;
}
}
/* 从表尾到下标i元素依次后移一个位置， 把i的位置空出来 */
for(j = L- >size - 1;
j >= i;
j--)
L- >list[j+1] = L->list[j];
/* 把x值赋给下标为i的元素 */
L- >list[i] = x;
/* 线性表长度增加1 */
L- >size++;
return;
}
/* 13.从线性表L中删除表头元素并返回它，若删除失败则停止程序运行 */
elemType deleteFirstList(struct List *L)
{
elemType temp;
int i;
if(L - >size == 0){
printf( "线性表为空，不能进行删除操作！ ");
exit(1);
}
temp = L- >list[0];
for(i = 1;
i< L->size;
i++)
L- >list[i-1] = L->list[i];
L- >size--;
return temp;
}
/* 14.从线性表L中删除表尾元素并返回它，若删除失败则停止程序运行 */
elemType deleteLastList(struct List *L)
{
if(L - >size == 0){
printf( "线性表为空，不能进行删除操作！ ");
exit(1);
}
L- >size--;
return L - >list[L->size];
/* 返回原来表尾元素的值 */
}
/* 15.从线性表L中删除第pos个元素并返回它，若删除失败则停止程序运行 */
elemType deletePosList(struct List *L, int pos)
{
elemType temp;
int i;
if(pos< 1 || pos > L->size){/* pos越界则删除失败 */
printf( "pos值越界，不能进行删除操作！ ");
exit(1);
}
temp = L- >list[pos-1];
for(i = pos;
i< L->size;
i++)
L- >list[i-1] = L->list[i];
L- >size--;
return temp;
}
/* 16.从线性表L中删除值为x的第一个元素，若成功返回1，失败返回0 */
int deleteValueList(struct List *L, elemType x)
{
int i, j;
/* 从线性表中顺序查找出值为x的第一个元素 */
for(i = 0;
i< L->size;
i++){
if(L- >list[i] == x){
break;
}
}
/* 若查找失败，表明不存在值为x的元素，返回0 */
if(i == L- >size){
return 0;
}
/* 删除值为x的元素L- >list[i] */
for(j = i + 1;
j< L->size;
j++){
L- >list[j-1] = L->list[j];
}
L- >size--;
return 1;
}
/************************************************************************/
void main()
{
int a[10] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
int i;
struct List L;
initList( &L, 5);
for(i = 0;
i< 10;
i++){
insertLastList( &L, a[i]);
}
insertPosList( &L, 11, 48);
insertPosList(&L, 1, 64);
printf( "%d ", getElem(&L, 1));
traverseList( &L);
printf( "%d ", findList(&L, 10));
updatePosList( &L, 3, 20);
printf( "%d ", getElem(&L, 3));
traverseList( &L);
deleteFirstList( &L);
deleteFirstList(&L);
deleteLastList( &L);
deleteLastList(&L);
deletePosList( &L, 5);
;
deletePosList(&L, 7);
printf( "%d ", sizeList(&L));
printf( "%d ", emptyList(&L));
traverseList( &L);
clearList( &L);
return 0;
}
#include
#include
#define NN 12
#define MM 20
typedef int elemType ;
/************************************************************************/
/*以下是关于线性表链接存储（单链表）操作的16种算法*/
/************************************************************************/
struct sNode{/* 定义单链表结点类型 */
elemType data;
struct sNode *next;
};
/* 1.初始化线性表，即置单链表的表头指针为空 */
void initList(struct sNode* *hl)
{
*hl = NULL;
return;
}
/* 2.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */
void clearList(struct sNode* *hl)
{
/* cp和np分别作为指向两个相邻结点的指针 */
struct sNode *cp, *np;
cp = *hl;
/* 遍历单链表，依次释放每个结点 */
while(cp != NULL){
np = cp- >next;
/* 保存下一个结点的指针 */
free(cp);
cp = np;
}
*hl = NULL;
/* 置单链表的表头指针为空 */
return;
}
/* 3.返回单链表的长度 */
int sizeList(struct sNode *hl)
{
int count = 0;
/* 用于统计结点的个数 */
while(hl != NULL){
count++;
hl = hl- >next;
}
return count;
}
/* 4.检查单链表是否为空，若为空则返回１，否则返回０ */
int emptyList(struct sNode *hl)
{
if(hl == NULL){
return 1;
}else{
return 0;
}
}
/* 5.返回单链表中第pos个结点中的元素，若pos超出范围，则停止 程序运行 */
elemType getElem(struct sNode *hl, int pos)
{
int i = 0;
/* 统计已遍历的结点个数 */
if(pos< 1){
printf( "pos值非法，退出运行！ ");
exit(1);
}
while(hl != NULL){
i++;
if(i == pos){
break;
}
hl = hl- >next;
}
if(hl != NULL){
return hl- >data;
}else{
printf( "pos值非法，退出运行！ ");
exit(1);
}
}
/* 6.遍历一个单链表 */
void traverseList(struct sNode *hl)
{
while(hl != NULL){
printf( "%5d", hl->data);
hl = hl- >next;
}
printf( " ");
return;
}
/* 7.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */
elemType* findList(struct sNode *hl, elemType x)
{
while(hl != NULL){
if(hl- >data =https://www.it610.com/article/= x){
return&hl->data;
}else{
hl = hl- >next;
}
}
return NULL;
}
/* 8.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */
int updatePosList(struct sNode *hl, int pos, elemType x)
{
int i = 0;
struct sNode *p = hl;
while(p != NULL){/* 查找第pos个结点 */
i++;
if(pos == i){
break;
}else{
p = p- >next;
}
}
if(pos == i){
p- >data = https://www.it610.com/article/x;
return 1;
}else{
return 0;
}
}
/* 9.向单链表的表头插入一个元素 */
void insertFirstList(struct sNode* *hl, elemType x)
{
struct sNode *newP;
newP = malloc(sizeof(struct sNode));
if(newP == NULL){
printf( "内存分配失败，退出运行！ ");
exit(1);
}
newP- >data = https://www.it610.com/article/x;
/* 把x的值赋给新结点的data域 */
/* 把新结点作为新的表头结点插入 */
newP- >next = *hl;
*hl = newP;
return;
}
/* 10.向单链表的末尾添加一个元素 */
void insertLastList(struct sNode* *hl, elemType x)
{
struct sNode *newP;
newP = malloc(sizeof(struct sNode));
if(newP == NULL){
printf( "内在分配失败，退出运行！ ");
exit(1);
}
/* 把x的值赋给新结点的data域，把空值赋给新结点的next域 */
newP- >data = https://www.it610.com/article/x;
newP- >next = NULL;
/* 若原表为空，则作为表头结点插入 */
if(*hl == NULL){
*hl = newP;
}
/* 查找到表尾结点并完成插入 */
else{
struct sNode *p = NULL;
while(p- >next != NULL){
p = p- >next;
}
p- >next = newP;
}
return;
}
/* 11.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回１，否则返回０ */
int insetPosList(struct sNode* *hl, int pos, elemType x){
int i = 0;
struct sNode *newP;
struct sNode *cp = *hl, *ap = NULL;
/* 对pos值小于等于０的情况进行处理 */
if(pos<= 0){
printf( "pos值非法，返回０表示插入失败！ ");
return 0;
}
/* 查找第pos个结点 */
while(cp != NULL){
i++;
if(pos == i){
break;
}else{
ap = cp;
cp = cp- >next;
}
}
/* 产生新结点，若分配失败，则停止插入 */
newP = malloc(sizeof(struct sNode));
if(newP == NULL){
printf( "内存分配失败，无法进行插入操作！ ");
return 0;
}
/* 把x的值赋给新结点的data域 */
newP- >data = https://www.it610.com/article/x;
/* 把新结点插入到表头 */
if(ap == NULL){
newP- >next = cp;
/* 或改为newP->next = *hl;
*/
*hl = newP;
}
/* 把新结点插入到ap和cp之间 */
else{
newP- >next = cp;
ap- >next = newP;
}
return 1;
/* 插入成功返回1 */
}
/* 12.向有序单链表中插入元素x结点，使得插入后仍然有序 */
void insertOrderList(struct sNode* *hl, elemType x)
{
/* 把单链表的表头指针赋给cp，把ap置空 */
struct sNode *cp = *hl, *ap = NULL;
/* 建立新结点 */
struct sNode *newP;
newP = malloc(sizeof(struct sNode));
if(newP == NULL){
printf( "内在分配失败，退出运行！ ");
exit(1);
}
newP- >data = https://www.it610.com/article/x;
/* 把x的值赋给新结点的data域 */
/* 把新结点插入到表头 */
if((cp == NULL) || (x< cp->data)){
newP- >next = cp;
*hl = newP;
return;
}
/* 顺序查找出x结点的插入位置 */
while(cp != NULL){
if(x< cp->data){
break;
}else{
ap = cp;
cp = cp- >next;
}
}
/* 把x结点插入到ap和cp之间 */
newP- >next = cp;
ap- >next = newP;
return;
}
/* 13.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止 程序运行 */
elemType deleteFirstList(struct sNode* *hl)
{
elemType temp;
struct sNode *p = *hl;
/* 暂存表头结点指针，以便回收 */
if(*hl == NULL){
printf( "单链表为空，无表头可进行删除，退出运行！ ");
exit(1);
}
*hl = (*hl)- >next;
/* 使表头指针指向第二个结点 */
temp = p- >data;
/* 暂存原表头元素，以便返回 */
free(p);
/* 回收被删除的表头结点 */
return temp;
/* 返回第一个结点的值 */
}
/* 14.从单链表中删除表尾结点并返回它的值，若删除失败则停止 程序运行 */
elemType deleteLastList(struct sNode* *hl)
{
elemType temp;
/* 初始化cp和ap指针，使cp指向表头结点，使ap为空 */
struct sNode *cp = *hl;
struct sNode *ap = NULL;
/* 单链表为空则停止运行 */
if(cp == NULL){
printf( "单链表为空，无表头进行删除，退出运行！ ");
exit(1);
}
/* 从单链表中查找表尾结点，循环结束时cp指向表尾结点，ap指向其前驱结点 */
while(cp- >next != NULL){
ap = cp;
cp = cp- >next;
}
/* 若单链表中只有一个结点，则需要修改表头指针 */
if(ap == NULL){
*hl = (*hl)- >next;
/* 或改为*hl = NULL;
*/
}
/* 删除表尾结点 */
else{
ap- >next = NULL;
}
/* 暂存表尾元素，以便返回 */
temp = cp- >data;
free(cp);
/* 回收被删除的表尾结点 */
return temp;
/* 返回表尾结点的值 */
}
/* 15.从单链表中删除第pos个结点并返回它的值，若删除失败则停止 程序运行 */
elemType deletePosList(struct sNode* *hl, int pos)
{
int i = 0;
elemType temp;
/* 初始化cp和ap指针，使cp指向表头结点，使ap为空 */
struct sNode *cp = *hl;
struct sNode *ap = NULL;
/* 单链表为空或pos值非法则停止运行 */
if((cp == NULL) || (pos<= 0)){
printf( "单链表为空或pos值不正确，退出运行！ ");
exit(1);
}
/* 从单链表中查找第pos个结点，找到后由cp指向该结点，由ap指向其前驱结点 */
while(cp != NULL){
i++;
if(i == pos){
break;
}
ap = cp;
cp = cp- >next;
}
/* 单链表中没有第pos个结点 */
if(cp == NULL){
printf( "pos值不正确，退出运行！ ");
exit(1);
}
/* 若pos等于1，则需要删除表头结点 */
if(pos == 1){
*hl = (*hl)- >next;
/* 或改为*hl = cp->next;
*/
}
/* 否则删除非表头结点，此时cp指向该结点，ap指向前驱结点 */
else{
ap- >next = cp->next;
}
/* 暂存第pos个结点的值，以便返回 */
temp = cp- >data;
free(cp);
/* 回收被删除的第pos个结点 */
return temp;
/* 返回在temp中暂存的第pos个结点的值 */
}
/* 16.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */
int deleteValueList(struct sNode* *hl, elemType x)
{
/* 初始化cp和ap指针，使cp指向表头结点，使ap为空 */
struct sNode *cp = *hl;
struct sNode *ap = NULL;
/* 从单链表中查找值为x的结点，找到后由cp指向该结点，由ap指向其前驱结点 */
while(cp != NULL){
if(cp- >data =https://www.it610.com/article/= x){
break;
}
ap = cp;
cp = cp- >next;
}
/* 若查找失败，即该单链表中不存在值为x的结点，则返回0 */
if(cp == NULL){
return 0;
}
/* 如果删除的是表头或非表头结点则分别进行处理 */
if(ap == NULL){
*hl = (*hl)- >next;
/* 或改为*hl= cp->next */
}else{
ap- >next = cp->next;
}
free(cp);
/* 回收被删除的结点 */
return 1;
/* 返回1表示删除成功 */
}
/************************************************************************/
int main(int argc, char* argv[])
{
int a[NN];
int i;
struct sNode *p, *h, *s;
srand(time(NULL));
initList( &p);
for(i = 0;
i< NN;
i++){
a[i] = rand()& MM;
}
printf( "随机数序列：");
for(i = 0;
i< NN;
i++){
printf( "%5d", a[i]);
}
printf( " ");
printf( "随机数逆序：");
for(i = 0;
i< NN;
i++){
insertFirstList( &p, a[i]);
}
traverseList(p);
printf( "单链表长度：%5d ", sizeList(p));
for(h = p;
h != NULL;
h = h- >next){
while(deleteValueList( &(h->next), h->data)){
;
}
}
printf( "去除重复数：");
traverseList(p);
printf( "单链表长度：%5d ", sizeList(p));
h = NULL;
for(s = p;
s != NULL;
s = s- >next){
insertOrderList( &h, s->data);
}
printf( "有序表序列：");
traverseList(h);
clearList( &p);
system( "pause");
return 0;
}
