c语言实现线性结构（数组与链表）

由于这两天看了数据结构，所以又把大学所学的c语言和指针"挂"起来了。

本人菜鸟一枚请多多指教。下面是我这两天学习的成果（数组和链表的实现，用的是c语言哦！哈哈）。

（一）数组的实现和操作。代码如下：

#include <stdio.h>

#include <malloc.h>

#include <stdlib.h>

struct Array{

int length;//数组长度

int * pBase;//存放数组首元素的地址

int cnt;//有效元素的个数

};

void init_arr(struct Array * pArray,int length);//初始化数组

bool append_arr(struct Array * pArray,int val);//向数组末尾添加元素

bool insert_arr(struct Array * pArray,int index,int val);//在数组的某个位置插入元素

bool delete_arr(struct Array * pArray,int index,int * deleteVal);//删除数组某个位置的元素

int get(struct Array * pArray, int index);//获取数组某个位置的元素

bool is_empty(struct Array * pArray);//判断数组是否为空

bool is_full(struct Array * pArray);//判断数组是否满了

void sort_arr(struct Array * pArray);//对数组进行排序

void show_arr(struct Array * pArray);//输出数组元素

void inversion_arr(struct Array * pArray);//倒置数组元素

void main(void){

struct Array array;

int deleteVal;

init_arr(&array,6);

append_arr(&array,22);

append_arr(&array,-22);

//append_arr(&array,3);

insert_arr(&array,2,333);

append_arr(&array,1);

append_arr(&array,33);

append_arr(&array,1);

append_arr(&array,-2);

show_arr(&array);

if(delete_arr(&array,2,&deleteVal)){

printf("删除的元素是%d\n",deleteVal);

}

show_arr(&array);

if(get(&array,4)!=-1){

printf("取出的元素为%d\n",get(&array,4));

}

sort_arr(&array);

show_arr(&array);

printf("-----\n");

inversion_arr(&array);

show_arr(&array);

}

//初始化数组

void init_arr(struct Array * pArray,int length){

pArray->pBase = (int *)malloc(sizeof(int)*length);

if(NULL == pArray->pBase){

printf("初始化数组失败\n");

exit(-1);

}else{

pArray->cnt = 0;

pArray->length = length;

}

}

//判断数组是否为空

bool is_empty(struct Array * pArray){

if(pArray->cnt == 0){

return true;

}else{

return false;

}

}

//判断数组是否满了

bool is_full(struct Array * pArray){

if(pArray->cnt == pArray->length){

return true;

}else{

return false;

}

}

//向数组末尾添加元素

bool append_arr(struct Array * pArray,int val){

if(!is_full(pArray)){

pArray->pBase[pArray->cnt]= val;

(pArray->cnt)++;

return true;

}

else{

//printf("数组已满无法插入\n");

return false;

}

}

//输出数组元素

void show_arr(struct Array * pArray){

if(is_empty(pArray)){

printf("数组为空\n");

}else{

for(int i=0;i<pArray->cnt;i++){

printf("%d\n",pArray->pBase[i]);

}

}

}

//在数组的某个位置插入元素

bool insert_arr(struct Array * pArray,int index,int val){

if(index>(pArray->cnt)+1 || index<=0 || index==pArray->length || is_full(pArray)){

return false;

}else{

for(int i=pArray->cnt-1;i>=index-1;i--){

pArray->pBase[i+1] = pArray->pBase[i];

}

pArray->pBase[index-1] = val;

pArray->cnt++;

return true;

}

}

//删除数组某个位置的元素

bool delete_arr(struct Array * pArray,int index,int * deleteVal){

if(index<=0 || index>pArray->cnt || is_empty(pArray)){

return false;

}else{

*deleteVal = pArray->pBase[index-1];

for(int i = index;i<pArray->cnt;i++)

{

pArray->pBase[i-1] = pArray->pBase[i];

}

pArray->cnt--;

return true;

}

}

//获取数组某个位置的元素

int get(struct Array * pArray,int index){

if(index<=0 || is_empty(pArray) || index > pArray->cnt){

return -1;

}else{

return pArray->pBase[index-1];

}

}

//对数组进行排序

void sort_arr(struct Array * pArray){

if(is_empty(pArray)){

printf("此数组为空不能排序\n");

}else{

int t;

for(int i = 0;i<pArray->cnt-1;i++){

for(int j = i+1;j<pArray->cnt;j++){

if(pArray->pBase[j]<pArray->pBase[i]){

t = pArray->pBase[i];

pArray->pBase[i] = pArray->pBase[j];

pArray->pBase[j] = t;

}

}

}

}

}

//倒置数组元素

void inversion_arr(struct Array * pArray){

if(!is_empty(pArray) || !pArray->cnt ==1){

int i = 0;

int j = pArray->cnt-1;

int t;

while(i<j){

t = pArray->pBase[i];

pArray->pBase[i] = pArray->pBase[j];

pArray->pBase[j] = t;

i++;

j--;

}

}

}

运行结果如下：

（二）链接的实现和操作。代码如下：

#include <stdio.h>

#include <malloc.h>

#include <stdlib.h>

typedef struct Node{

int data;

Node * pNext;

}NODE,*PNODE;

//初始化链表

PNODE createList(int);

//遍历链表

void traverse_list(PNODE);

//判断链表是否为空

bool is_empty(PNODE);

//返回链表的长度

int length_list(PNODE);

//向链表中插入节点

bool insert_list(PNODE,int,int);

//删除某个节点

bool delete_list(PNODE,int,int *);

//为链表排序

void sort_list(PNODE);

//主函数

void main(void){

int leng;

PNODE pHead;

int val;

printf("请您输入链表的长度\n");

scanf("%d",&leng);

pHead = createList(leng);

//traverse_list(pHead);

if(is_empty(pHead)){

printf("链表为空\n");

}

//printf("链表的长度为%d\n",length_list(pHead));

//sort_list(pHead);

insert_list(pHead,3,111);

traverse_list(pHead);

if(delete_list(pHead,3,&val)){

printf("删除的节点为%d\n",val);

}

traverse_list(pHead);

}

//初始化链表

PNODE createList(int leng){

PNODE pHead;

pHead = (NODE *)malloc(sizeof(NODE));

if(NULL == pHead){

printf("初始化链表失败\n");

exit(-1);

}

PNODE pTail = pHead;

pTail->pNext = NULL;

for(int i=1;i<=leng;i++){

int val;

PNODE pNew = (NODE *)malloc(sizeof(NODE));

printf("请输入第%d个值:",i);

scanf("%d",&val);

pNew->data = val;

pNew->pNext = NULL;

pTail->pNext = pNew;

pTail = pNew;

}

return pHead;

}

//遍历链表

void traverse_list(PNODE pHead){

PNODE p = pHead;

if(p->pNext == NULL){

printf("链表为空\n");

}

while(p->pNext != NULL){

p = p->pNext;

printf("%d\n",p->data);

}

}

//判断链表是否为空

bool is_empty(PNODE pHead){

if(pHead->pNext == NULL){

return true;

}else{

return false;

}

}

//返回链表的长度

int length_list(PNODE pHead){

PNODE p = pHead;

int leng = 0;

while(p->pNext != NULL){

p = p->pNext;

leng++;

}

return leng;

}

//向链表中插入节点

bool insert_list(PNODE pHead,int index,int val){

int i = 0;

PNODE p = pHead;

while(p->pNext!=NULL && i<index-1){

p = p->pNext;//p->1;p->2

i++;//1;2

}

if(p->pNext == NULL ||  i>index-1){

return false;

}

PNODE pNew = (PNODE)malloc(sizeof(NODE));

if(pNew == NULL){

printf("初始化节点失败\n");

exit(-1);

}

pNew->data = val;

pNew->pNext = p->pNext;

p->pNext = pNew;

return true;

}

//删除某个节点

bool delete_list(PNODE pHead,int index,int * val){

int i = 0;

PNODE p = pHead;

while(p->pNext!=NULL && i<index-1){

p = p->pNext;//p->1;p->2

i++;//1;2

}

if(p->pNext == NULL ||  i>index-1){

return false;

}

PNODE delNode = p->pNext;

*val = delNode->data;

p->pNext = delNode->pNext;

free(delNode);

return true;

}

//为链表排序

void sort_list(PNODE pHead){

int t,i,j;

PNODE p,q;

for(i=0,p = pHead;i<length_list(pHead);i++,p=p->pNext){

for(j=i+1,q = p->pNext;j<=length_list(pHead);j++,q = q->pNext){

if(p->data > q->data){

t = p->data;

p->data = q->data;

q->data = t;

}

}

}

}

运行结果如下：