首页 > 代码库 > c语言实现线性结构（数组与链表）
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 = http://www.mamicode.com/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 = http://www.mamicode.com/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 = http://www.mamicode.com/q->data;
q->data = http://www.mamicode.com/t;
}
}
}
}
运行结果如下：
c语言实现线性结构（数组与链表）