上周看了3次数据结构的视频，现在看起来，尽然能听的懂🤔，貌似记得大学的时候 数据结构 这门课程，60分压线及格过的呐😭。。。
下面来看看这部分的代码吧，扔图哈，比着自己敲一下，肯定能加深印象，你比伸手党好多了。。。关于这部分代码估计没人讲或者没有视频是看不懂的，那就辛苦下，多看几遍，熟读唐诗3百首，不会作诗也会吟。。。
记得要用 Xcode 中的命令行工具建立工程哈~
链表
呃~~貌似不能全部截图
好吧，下面放代码：
//
// main.m
// 链表创建和遍历
//
// Created by 小伴 on 16/7/6.
// Copyright © 2016年 huangqimeng. All rights reserved.
//
#import <Foundation/Foundation.h>
#include <stdio.h>
#include <malloc/malloc.h>
#include <stdlib.h>
/**
* 节点的数据类型：包括数据域和指针域
*/
typedef struct Node {
int data; //数据域
struct Node *pNext; //指针域
} NODE, *PNODE; //NODE 等价于 struct Node ； PNODE 等价于 struct Node *
/**
* 函数声明
*/
/** 创建 */
PNODE create_list(void);
/** 遍历 */
void traverse_list(PNODE pHead);
/** 判空 */
bool is_empty(PNODE pHead);
/** 长度 */
int length_list(PNODE);
/** 插入 */
bool insert_list(PNODE, int, int);
/** 删除 */
bool delete_list(PNODE, int, int *);
/** 排序 */
void sort_list(PNODE);
int main(int argc, const char * argv[]) {
@autoreleasepool {
PNODE pHead = NULL; //等价于struct Node * pHead = NULL;
pHead = create_list(); //创建一个非循环单链表，并将该链表的头结点的地址赋给 pHead
traverse_list(pHead); //遍历
/*
insert_list(pHead, 3, 45);
traverse_list(pHead);
*/
int val;
if (delete_list(pHead, 3, &val)) {
printf("删除成功，删除的元素是：%d\n", val);
} else {
printf("删除失败，删除的元素不存在！\n");
}
traverse_list(pHead);
int len = length_list(pHead);
printf("长度len = %d\n", len);
sort_list(pHead);
traverse_list(pHead);
/*
if (is_empty(pHead)) {
printf("链表为空\n");
} else {
printf("链表不空\n");
}*/
}
return 0;
}
/**
* 创建非循环单链表
*/
PNODE create_list() {
int len; //存放有效节点的个数
int i;
int val; //临时存放用户输入的节点的值
//分配一个不存放有效数据的头节点
PNODE pHead = (PNODE)malloc(sizeof(NODE));
if (pHead == NULL) {
printf("分配失败，程序终止\n");
exit(-1); //程序终止
}
PNODE pTail = pHead;
pTail->pNext = NULL;
printf("输入需要生成的链表的节点个数：len = ");
scanf("%d", &len);
for (i = 0; i < len; i++) {
printf("输入第 %d 个节点的值：", i + 1);
scanf("%d", &val);
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (pNew == NULL) {
printf("分配失败，程序终止\n");
exit(-1);
}
pNew->data = val;
pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;
}
return pHead;
}
/**
* 遍历非循环单链表
*/
void traverse_list(PNODE pHead) {
PNODE p = pHead->pNext;
while (p != NULL) {
printf("%d ", p->data);
p = p->pNext;
}
printf("\n");
}
/**
* 判空
*/
bool is_empty(PNODE pHead) {
if (pHead->pNext == NULL) {
return true;
} else {
return false;
}
}
/**
* 长度
*/
int length_list(PNODE pHead) {
PNODE p = pHead->pNext;
int len = 0;
while (p!= NULL) {
len++;
p=p->pNext;
}
return len;
}
/**
* 排序
*/
void sort_list(PNODE pHead) {
int i, j, t;
int len = length_list(pHead);
PNODE p, q;
for (i = 0, p = pHead->pNext; i < len-1; i++, p = p->pNext) {
for (j = i+1, q = p->pNext; j < len; j++, q = q->pNext) {
if (p->data > q->data) {//类似数组中的a[i] > a[j]
t = p->data; //t = a[i];
p->data = q->data; //a[i] = a[j];
q->data = t; //a[j] = t;
}
}
}
}
/**
* 在pHead所指向链表的第pos个节点的前面插入一个新的节点，该节点的值是val，并且pos的值是从1开始的
*/
///经典的算法
bool insert_list(PNODE pHead, int pos, int val) {
int i = 0;
PNODE p = pHead;
while (p != NULL && i < pos - 1) {
p = p->pNext;
++i;
}
//不需要判断链表空、满、算长度
if (i > pos - 1 || p == NULL) {
return false;
} else {
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (pNew == NULL) {
printf("动态内存分配失败！\n");
exit(-1);
} else {
pNew->data = val;
PNODE temp = p->pNext;
p->pNext = pNew;
pNew->pNext = temp;
return true;
}
}
}
bool delete_list(PNODE pHead, int pos, int *pVal) {
int i = 0;
PNODE p = pHead;
while (p->pNext != NULL && i < pos - 1) {
p = p->pNext;
++i;
}
if (i > pos - 1 || p->pNext == NULL) {
return false;
} else {
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (pNew == NULL) {
printf("动态内存分配失败！\n");
exit(-1);
} else {
PNODE temp = p->pNext;
*pVal = temp->data;
//删除p节点后面的节点
p->pNext = p->pNext->pNext;
free(temp);
temp = NULL;
return true;
}
}
}
自己研究去吧。。。祝你早日看的懂~
链表的插入和删除已经更新了，最强链表的算法拿走不谢，最后插入和删除的算法特别经典，好好看看争取弄懂他。
碎觉😴
