线性表的实现
最近一直在看数据结构方面的书,最先遇到的就是线性表,于是乎照猫画虎的写了一下线性表的代码.可能很多地方还有可以改进的地方,希望各位能在下面留言,非常期待各位高手宝贵的意见.
个人觉得比较难的几个地方是:
1.指针的使用.你会突然发现C学的简单的指针不够用了,需要学更多的关于指针的东西;
2.关于数组角标的计算.这种东西拿特殊情况带一下就能算出来啦.
下面还是PO出我的代码,供大家交流学习
/*
Title: Array function practice(1)
Date：2016-9-29
Author: pengwill
*/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
// 定义一种结构叫做Arr
struct Arr{
int *pBase;//线性表的首地址
int cnt;//当前线性表的个数
int len;//线性表最多能容纳的元素个数
};
int comp(void const *a, void const *b){
return *(int*) a - *(int*) b;
}
void init_Arr(struct Arr * pArr, int length);//线性表的初始化
bool show_Arr(struct Arr * pArr); //打印线性表中的元素
bool is_empty(struct Arr * pArr); //判断线性表是否为空
bool scan_Arr(struct Arr * pArr, int n); //输入线性表的数据
bool del_elem(struct Arr * pArr,int n); // 删除线性表中某个元素
bool append_elem(struct Arr * pArr, int n);//在线性表最后追加一个元素
bool sort_Arr(struct Arr * pArr);//对线性表元素进行排序;
bool insert_elem(struct Arr* pArr,int pos,int n);
int main()
{
struct Arr arr;
init_Arr(&arr,10);
printf("%d %d
",arr.len,arr.cnt);
{
scan_Arr(&arr,8);
del_elem(&arr,8);
show_Arr(&arr);
append_elem(&arr,-100);
show_Arr(&arr);
sort_Arr(&arr);
show_Arr(&arr);
insert_elem(&arr,5,-10010);
show_Arr(&arr);
sort_Arr(&arr);
show_Arr(&arr);
}
return 0;
}
void init_Arr(struct Arr * pArr, int length)
{
pArr->pBase = (int*)malloc(sizeof(int) * length); //把操作系统请求分配的内部的首地址传给变量arr.pBase,完成初始化
/*但是还有可能出现意外情况，即向操作系统请求分配内存失败，那么需要判断一下*/
if(pArr->pBase == NULL){
exit(-1);
} else{
pArr->cnt = 0;
pArr->len = length;
printf("---------Initializtion Over---------
");
}
/*如果请求分配内存失败，那么程序终止，否则完成的数组的cnt(当前个数)和len(数组总长度)的初始化*/
}
bool show_Arr(struct Arr * pArr)
{
int i;
if(is_empty(pArr) == true ){
printf("---------The Array is empty!--------
");
}else {
printf("------The Array is NOT empty!-------
");
printf("------Now output the elements!------
");
for(i = 0;i<pArr->cnt;i++){
printf("%d
",pArr->pBase[i]); // 这里卡住了，pBase没写出来 回头看一下；
// 指针就是数组，数组就是指针，数组的单元就代表其地址
}
}
}
bool is_empty(struct Arr * pArr)
{
if(0 == pArr->cnt){
return true;
}else{
return false;
}
}
bool scan_Arr(struct Arr * pArr, int n)
{
int i;
if(n > pArr->len){ // 判断防止数据数量超出分配的内存
printf("-------------Error Number!-----------
");
return false;
}else{
for(i = 0;i<n;i++){
scanf("%d",&pArr->pBase[i]);//挨个读入数据
}
pArr->cnt = n;// 更新当前数据的个数
return true;
}
}
bool del_elem(struct Arr * pArr,int n)//删除第n个元素
{
int i;
if(n<= pArr->cnt){
pArr->pBase[n-1] = 0;
for(i = n-1;i<pArr->cnt;i++){
pArr->pBase[i] = pArr->pBase[i+1];
show_Arr(pArr);
}
(pArr->cnt)--;
return true;
}else{
return false;
}
}
bool append_elem(struct Arr * pArr, int n)
{
if(pArr->cnt == pArr->len){
printf("Sorry! The array is full!
");
return false;
} else{
pArr->pBase[pArr->cnt] = n;
pArr->cnt++;
return true;
}
}
bool sort_Arr(struct Arr * pArr)
{
if(pArr->cnt != 0){
qsort(pArr->pBase,pArr->cnt,sizeof(int),comp);
return true;
}else{
return false;
}
}
bool insert_elem(struct Arr* pArr,int pos,int n)
{
int i;
if(pos<=pArr->cnt && pArr->cnt <= pArr->len-1){
for(i = pArr->cnt-1;i>=pos -1 ;i--){
pArr->pBase[i+1] = pArr->pBase[i];
}
pArr->pBase[pos-1] = n;
pArr->cnt++;
return true;
} else{
return false;
}
}