首页 > 代码库 > 线性表实现——自动扩容实现
线性表实现——自动扩容实现
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 5 #define OK 1 6 #define ERROR 0 7 8 typedef struct { 9 int x; 10 int y; 11 }Point; 12 13 typedef struct { 14 Point *pt; 15 int length; 16 int size; 17 }AutoArrList; 18 19 //声明线性表所具有的方法 20 AutoArrList *CreateArrList(int nLength) //创建长为 nArrLength 的线性表 21 { 22 AutoArrList * l=(AutoArrList*)malloc(sizeof(AutoArrList)); 23 if (l == NULL) 24 return NULL; 25 Point * p= (Point*)calloc(nLength,sizeof(Point)); 26 if (p == NULL) 27 { 28 free(l); 29 return NULL; 30 } 31 32 l->pt = p; 33 l->length = 0; 34 l->size = nLength; 35 36 return l; 37 } 38 void DestroyArrList(AutoArrList *pArrList) //销毁线性表 pArrList 39 { 40 if (pArrList == NULL) 41 return; 42 free(pArrList->pt); 43 free(pArrList); 44 return; 45 } 46 void ClearArrList(AutoArrList *pArrList) //置空线性表 pArrList 47 { 48 //if (pArrList == NULL) 49 // return; 50 //pArrList->pt = NULL; 51 pArrList->length = 0; 52 return; 53 } 54 int IsEmptyArrList(AutoArrList *pArrList) //检测线性表是否为空 55 { 56 if (pArrList->length == 0) 57 return 1; 58 return 0; 59 } 60 int GetArrListLength(AutoArrList *pArrList) //获取线性表长度 61 { 62 return pArrList->length; 63 } 64 int GetArrListSize(AutoArrList *pArrList) //获取线性表总容量 65 { 66 return pArrList->size; 67 } 68 int GetArrListElement(AutoArrList *pArrList, int n, Point *pt) //获取线性表中第n个元素 69 { 70 if ((pArrList->length == 0) || (n < 1) || (n > pArrList->length)) 71 return ERROR; 72 pt->x = pArrList->pt[n - 1].x; 73 pt->y = pArrList->pt[n - 1].y; 74 75 return OK; 76 } 77 int FindElement(AutoArrList *pArrList, int nPos, Point *pt) //从 nPos 起查找 pt 第一次出现的位置 78 { 79 if ((pArrList->length == 0) || (nPos < 1) || (nPos > pArrList->length)) 80 return ERROR; 81 int i; 82 for (i = nPos - 1; i < pArrList->length; i++) 83 { 84 if ((pArrList->pt[i].x == pt->x) && (pArrList->pt[i].y == pt->y)) 85 return i + 1; 86 } 87 return ERROR; 88 } 89 int GetPriorElement(AutoArrList *pArrList, Point *pt, Point *prior_pt) //获取 pt 的前驱节点到 prior_pt 90 { 91 if (pArrList->length == 0) 92 return ERROR; 93 int i; 94 for (i = 1; i < pArrList->length; i++) 95 { 96 if ((pArrList->pt[i].x == pt->x) && (pArrList->pt[i].y == pt->y)) 97 { 98 prior_pt->x = pArrList->pt[i].x; 99 prior_pt->y = pArrList->pt[i].y;100 return OK;101 } 102 }103 return ERROR;104 }105 int GetNextElement(AutoArrList *pArrList, Point *pt, Point *next_pt) //获取 pt 的后继节点到 next_pt106 {107 if (pArrList->length == 0)108 return ERROR;109 int i;110 for (i = 0; i < pArrList->length-1; i++)111 {112 if ((pArrList->pt[i].x == pt->x) && (pArrList->pt[i].y == pt->y))113 {114 next_pt->x = pArrList->pt[i].x;115 next_pt->y = pArrList->pt[i].y;116 return OK;117 }118 }119 return ERROR;120 }121 int AppendToArrList(AutoArrList *pArrList, Point *pt) //将 pt 添加到线性表末尾处122 {123 if (pArrList->length == pArrList->size)124 {125 Point *p = (Point *)calloc(pArrList->length * 2, sizeof(Point));126 memcpy(p, pArrList->pt, pArrList->length);127 pArrList->size = pArrList->length * 2;128 free(pArrList->pt);129 pArrList->pt = p;130 }131 pArrList->pt[pArrList->length].x = pt->x;132 pArrList->pt[pArrList->length].y = pt->y;133 pArrList->length++;134 return OK;135 }136 int InsertToArrList(AutoArrList *pArrList, int nPos, Point *pt) //将 pt 插入到 nPos 处137 {138 int i;139 if ((pArrList->length == 0) || (nPos < 1) || (nPos > pArrList->length))140 return ERROR;141 if (pArrList->length == pArrList->size)142 {143 Point *p = (Point *)calloc(pArrList->length * 2, sizeof(Point));144 memcpy(p, pArrList->pt, pArrList->length);145 pArrList->size = pArrList->length * 2;146 free(pArrList->pt);147 pArrList->pt = p;148 }149 if (nPos <= pArrList->length)150 {151 for (i = pArrList->length; i > nPos - 1; i--)152 {153 pArrList->pt[i].x = pArrList->pt[i - 1].x;154 pArrList->pt[i].y = pArrList->pt[i - 1].y;155 }156 }157 pArrList->pt[nPos-1].x = pt->x;158 pArrList->pt[nPos-1].y = pt->y;159 pArrList->length++;160 return OK;161 }162 int DeleteFromArrList(AutoArrList *pArrList, int nPos) //删除线性表上位置为 nPos 的元素163 {164 int i;165 if ((pArrList->length == 0) || (nPos < 1) || (nPos > pArrList->length))166 return ERROR;167 if (nPos < pArrList->length)168 {169 for (i = nPos - 1; i < pArrList->length - 1; i++)170 {171 pArrList->pt[i].x = pArrList->pt[i + 1].x;172 pArrList->pt[i].y = pArrList->pt[i + 1].y;173 }174 }175 pArrList->length--;176 return OK;177 }178 void ForEachArrList(AutoArrList *pArrList, void(*func)(Point *pt)) //对线性表中每个元素执行 func 函数179 {180 if (pArrList->length == 0)181 return ;182 int i;183 for (i = 0; i < pArrList->length; i++)184 {185 func(&pArrList->pt[i]);186 }187 }188 int ArrListCpy(AutoArrList *pArrListDest, AutoArrList *pArrListSrc) //将线性表 pArrListSrc 复制到 pArrListDest189 {190 if (pArrListSrc->length == 0)191 return ERROR;192 if (pArrListSrc->length > pArrListDest->size)193 {194 free(pArrListDest->pt);195 Point *p = (Point *)malloc(pArrListSrc->length *sizeof(Point));196 pArrListDest->pt = p;197 pArrListDest->size = pArrListSrc->length;198 }199 memcpy(pArrListDest->pt, pArrListSrc->pt, pArrListSrc->length * sizeof(Point));200 pArrListDest->length = pArrListSrc->length;201 return OK;202 }203 int ArrListCat(AutoArrList *pArrListDest, AutoArrList *pArrListSrc) //将线性表 pArrListSrc 连接到 pArrListDest 的末尾204 {205 if (pArrListSrc->length == 0)206 return OK;207 if (pArrListDest->size < (pArrListDest->length + pArrListSrc->length))208 {209 int len = pArrListDest->length + pArrListSrc->length;210 Point *p = (Point *)calloc(len ,sizeof(Point));211 memcpy(p, pArrListDest->pt, pArrListDest->length * sizeof(Point));212 free(pArrListDest->pt);213 pArrListDest->pt = p;214 pArrListDest->size = len;215 }216 memcpy(pArrListDest + pArrListDest->length, pArrListSrc->pt, pArrListSrc->length * sizeof(Point));217 pArrListDest->length += pArrListSrc->length;218 return OK;219 }220 void display(Point *pt)221 {222 printf("(%d,%d) ", pt->x, pt->y);223 }
线性表实现——自动扩容实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。