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;

}

}

}

}

運行結果如下：