温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

C语言实现动态顺序表的实现代码

发布时间:2020-08-31 02:36:51 来源:脚本之家 阅读:247 作者:lqh 栏目:编程语言

C语言实现动态顺序表的实现代码

顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

静态实现:结构体内部只需两个成员,其中一个为固定大小(MAX)的数组,用来存放我们的数据。数组大小我们可以通过在头文件中改变MAX的值来改变。

动态实现:在内存中开辟一块空间,可以随我们数据数量的增多来扩容。

来看看动态的顺序表实现:

1.seqlist.h

#define _CRT_SECURE_NO_WARNINGS 1 
 
#ifndef __SEQLIST_H__ 
#define __SEQLIST_H__ 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <assert.h> 
 
typedef int DataType; 
 
#define DEFAULT_SZ 3 
#define INC_SZ 2 
 
typedef struct SeqList 
{ 
 DataType *data; 
 int sz; 
 int capacity; 
}SeqList,*pSeqList; 
 
void InitSeqList(pSeqList pList); 
void PushBack(pSeqList pList,DataType d); 
void PopBack(pSeqList pList); 
void PushFront(pSeqList pList, DataType d); 
void PopFront(pSeqList pList); 
int Find(pSeqList pList, DataType d); 
void Remove(pSeqList pList, DataType d); 
void RemoveAll(pSeqList pList, DataType d); 
void BubbleSort(pSeqList pList); 
int BinarySearch(pSeqList pList, DataType d); 
void PrintfSeqList(pSeqList pList); 
void Insert(pSeqList pList, int pos, DataType d); 
void ReverseList(pSeqList pList); 
void DestroySeqList(pSeqList pList); 
 
 
 
 
#endif//__SEQLIST_H__ 

2.seqlist.c

#define _CRT_SECURE_NO_WARNINGS 1 
 
#include "seqlist.h" 
 
void InitSeqList(pSeqList pList) 
{ 
 pList->sz = 0; 
 pList->data = (DataType*)malloc(sizeof(DataType)*DEFAULT_SZ); 
 if (pList->data == NULL) 
 { 
  perror("malloc"); 
  return; 
 } 
 memset(pList->data, 0, sizeof(DataType)*DEFAULT_SZ); 
} 
void CheckCapacity(pSeqList pList) 
{ 
 assert(pList); 
 if (pList->sz == pList->capacity) 
 { 
  DataType*ret = (DataType*)realloc(pList->data, sizeof(DataType)*(pList->capacity + INC_SZ)); 
  if (ret == NULL) 
  { 
   perror("realloc"); 
  } 
  pList->data = ret; 
  pList->capacity += INC_SZ; 
 
 } 
} 
void PushBack(pSeqList pList, DataType d) 
{ 
 assert(pList); 
 if (pList->sz == pList->capacity) 
 { 
  CheckCapacity(pList); 
 } 
 pList->data[pList->sz] = d; 
 pList->sz++; 
} 
void PopBack(pSeqList pList) 
{ 
 int i = 0; 
 assert(pList); 
 if (pList->sz == 0) 
 { 
  printf("顺序表为空:<"); 
  return; 
 } 
 pList->sz--; 
} 
void PushFront(pSeqList pList, DataType d) 
{ 
 int i = 0; 
 assert(pList); 
 if (pList->sz == pList->capacity) 
 { 
  CheckCapacity(pList); 
 } 
 for (i = pList->sz; i >= 1; i--) 
 { 
  pList->data[i] = pList->data[i - 1]; 
 } 
 pList->data[0] = d; 
 pList->sz++; 
} 
void PopFront(pSeqList pList) 
{ 
 int i = 0; 
 assert(pList); 
 for (i = 0; i < pList->sz; i++) 
 { 
  pList->data[i] = pList->data[i + 1]; 
 } 
 pList->sz--; 
} 
int Find(pSeqList pList, DataType d) 
{ 
 int i = 0; 
 assert(pList); 
 while (i < pList->sz) 
 { 
  if (pList->data[i] == d) 
  { 
   return i; 
  } 
  else 
  { 
   i++; 
  } 
 } 
 return -1; 
} 
void Remove(pSeqList pList, DataType d) 
{ 
 int i = 0; 
 int pos = 0; 
 assert(pList); 
 while (pList->data[pos=Find(pList,d)]==d) 
 { 
  for (i = pos; i < pList->sz-1; i++) 
  { 
   pList->data[i] = pList->data[i + 1]; 
  } 
  pList->sz--; 
 } 
} 
void RemoveAll(pSeqList pList, DataType d) 
{ 
 int i = 0; 
 int pos = 0; 
 assert(pList); 
 while ((pos = Find(pList, d)) != -1) 
 { 
  for (i = pos; i < pList->sz - 1; i++) 
  { 
   pList->data[i] = pList->data[i + 1]; 
  } 
  pList->sz--; 
 } 
} 
void BubbleSort(pSeqList pList) 
{ 
 int i = 0; 
 assert(pList); 
 for (i = 0; i < pList->sz - 1; i++) 
 { 
  int j = 0; 
  for (j = 0; j < pList->sz - i - 1; j++) 
  { 
   if (pList->data[j]>pList->data[j + 1]) 
   { 
    DataType tmp = pList->data[j]; 
    pList->data[j] = pList->data[j + 1]; 
    pList->data[j + 1] = tmp; 
   } 
  } 
 } 
} 
int BinarySearch(pSeqList pList, DataType d) 
{ 
 int left = 0; 
 int right = pList->sz - 1; 
 assert(pList); 
 while (left <= right) 
 { 
  int mid = left - ((left - right) >> 1); 
  if (d > pList->data[mid]) 
  { 
   left = mid + 1; 
  } 
  else if (d < pList->data[mid]) 
  { 
   right = mid - 1; 
  } 
  else 
   return mid; 
 } 
 return -1; 
} 
void PrintfSeqList(pSeqList pList) 
{ 
 int i = 0; 
 for (i = 0; i < pList->sz; i++) 
 { 
  printf("%d ", pList->data[i]); 
 } 
} 
void Insert(pSeqList pList, int pos, DataType d) 
{ 
 int i = 0; 
 if (pList->sz == pList->capacity) 
 { 
  CheckCapacity(pList); 
 } 
 for (i = pList->sz - 1; i >= pos; i--) 
 { 
  pList->data[i + 1] = pList->data[i]; 
 } 
 pList->data[pos] = d; 
 pList->sz++; 
} 
void ReverseList(pSeqList pList) 
{ 
 int left = 0; 
 int right = pList->sz - 1; 
 assert(pList); 
 while (left < right) 
 { 
  DataType tmp = pList->data[left]; 
  pList->data[left] = pList->data[right]; 
  pList->data[right] = tmp; 
  left++; 
  right--; 
 } 
} 
void DestroySeqList(pSeqList pList) 
{ 
 free(pList->data); 
 pList->data = NULL; 
} 

3.test.c

#define _CRT_SECURE_NO_WARNINGS 1 
#include "seqlist.h" 
 
//void Test() 
//{ 
// SeqList *List; 
// InitSeqList(&List); 
// PushBack(&List, 1); 
// PushBack(&List, 2); 
// PushBack(&List, 3); 
// PushBack(&List, 4); 
// PushBack(&List, 5); 
// PopBack(&List); 
// printf("%d ", Find(&List, 2)); 
// PrintfSeqList(&List); 
//} 
 
void Test2() 
{ 
 SeqList List; 
 InitSeqList(&List); 
 PushBack(&List, 1); 
 PushBack(&List, 2); 
 PushBack(&List, 3); 
 PushBack(&List, 4); 
 PushBack(&List, 5); 
 PushFront(&List, 5); 
 PushFront(&List, 2); 
 PushFront(&List, 3); 
 //PopFront(&List); 
 RemoveAll(&List, 5); 
 //BubbleSort(&List); 
 //BinarySearch(&List, 3); 
 PrintfSeqList(&List); 
} 
int main() 
{ 
 Test2(); 
 system("pause\n"); 
 return 0; 
} 

静态顺序表的实现:https://www.jb51.net/article/120875.htm

以上就是动态实现顺序表的实例,如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI