数据结构之线性表
目录
- 概述
- 顺表
特点
顺表的操作
准备
创建顺表
查询顺表长度
遍历顺表
按序查找
按值查找
插入
删除
- 链表
- 实际使用
概述
线性表是一种线性的存储结构，表头有唯一后继元素，表尾有唯一前驱元素，表中的元素既有前驱又有后继
顺表
特点
逻辑上存储位置相邻的元素其物理存储位置也相邻
顺表的操作
准备
//定义存储元素的数据类型
typedef int DataType;
//定义数组最大长度
#define MAX_LENGTH 5
//全局定义记录当前的顺表长度（<=最大长度)
int list_length;
创建顺表
DataType *createList(){
int array_dataSource[MAX_LENGTH] = {3,2,5,8,9};
list_length = 0;
DataType *array = (DataType *)malloc(MAX_LENGTH*sizeof(DataType));
for (int i=0; i<MAX_LENGTH; i++) {
*(array+i) = array_dataSource[i];
list_length+=1;
}
NSLog(@"顺表创建成功!");
return array;
}
查询顺表长度
int listLength(int *array){
return list_length;
}
遍历顺表
void traverseArray(DataType *array){
if (list_length == 0) {
NSLog(@"空数组!");
return;
}
for(int i=0;i<list_length;i++){
printf("%d\t",*(array+i));
}
printf("\n")
}
按序查找
DataType searchByOrder(int order,int *array){
if(order>0&&order<=listLength(array)&&list_length!=0){
NSLog(@"在序列为%d上的数值为%d",order,*(array+order-1));
return *(array+order-1);
}else{
NSLog(@"输入有误！");
return -1;
}
return -1;
}
按值查找
int searchByValue(int value,int *array){
for(int i=0;i<list_length;i++){
if(*(array+i)==value){
NSLog(@"数值为%d的序号为%d",value,i+1);
return i+1;
}else{
i+=1;
}
}
NSLog(@"没有找到！");
return -1;
}
插入（从插入位置开始的每个元素向后移一位，循环从末尾开始到前面）
BOOL insertValueIntoList(int order,int value,int *array){
if(list_length>=MAX_LENGTH){
NSLog(@"数组已满！");
}
else if(order<=0||order>list_length){
NSLog(@"插入序列有误!");
}
else{
for(int i=list_length;i>order-1;i--){
*(array+i)=*(array+i-1);
}
*(array+order-1)=value;
list_length+=1;
NSLog(@"插入成功!");
return YES;
}
return NO;
}
删除（从删除位置开始把后一位向前移一位，循环从删除位置开始，当最末尾元素的前一位）
BOOL deleteValueByOrder(int order,int *array){
if(list_length<=0){
NSLog(@"数组为空!");
return NO;
}
else if (order<=0||order>list_length){
NSLog(@"删除位置有错!");
return NO;
}
else{
for(int i=order-1;i<list_length-1;i++){
*(array+i)=*(array+i+1);
}
list_length-=1;
NSLog(@"删除成功!");
return YES;
}
return NO;
}
链表
特点
逻辑上存储位置相邻的元素其物理存储位置不一定相邻
链表的操作
准备
定义节点的结构体
typedef struct Node{
DataType data; //数据域
struct Node *next; //指针域
}node;
新建链表
node *head = (node *)malloc(sizeof(node));
head->next = nil;
node *p = head;
int goOn = YES;
while(goOn){
node *n = (node *)malloc(sizeof(node));
NSLog("请输入");
scanf("%d",&n->data);
n->next = p->next;
p->next = n;
p=p->next;
goOn = n->data;
}
return head;
遍历链表
void traverseList(node *head){
node *p = head;
while (p->next!=nil) {
p=p->next;
NSLog(@"%d",p->data);
}
}
查询链表长度
int listLength(node *head){
node *p = head;
int i=0;
while (p->next!=nil) {
i+=1;
p=p->next;
}
NSLog(@"链表的长度为%d",i);
return i;
}
按序查找
int searchByOrder(node *head,int order){
node *p = head;
int i=0;
while (p->next!=nil&&i<=order) {
p=p->next;
i+=1;
}
if (i>=order) {
NSLog(@"序列为%d的数值为%d",i,p->data);
return p->data;
}else{
return 0;
}
}
按值查找
int searchByValue(node *head,DataType value){
node *p = head;
int i=0;
while (p->next!=nil) {
p=p->next;
i+=1;
if (p->data == value) {
NSLog(@"数值为%d的序列为%d",value,i);
return i;
}
}
//没有找到
return 0;
}
插入
头插入
尾插入
void insertValue(node *head,int value,int order){
node *p = head;
int i=0;
while (p->next!=nil&&i<order-1) {
p=p->next;
i+=1;
}
if (i>=order-1) {
node *temp = (node *)malloc(sizeof(node));
temp->data = value;
temp->next = p->next;
p->next = temp;
NSLog(@"插入成功！");
}else{
NSLog(@"插入失败!");
}
return;
}
删除
int deleteValue(node *head,int order){
node *p = head;
int i=0;
int delete_data = 0;
while (p->next!=nil&&i<order-1) {
p=p->next;
i+=1;
}
if (i>=order-1) {
delete_data = p->next->data;
p->next=p->next->next;
NSLog(@"删除成功!");
return delete_data;
}else{
NSLog(@"删除失败!");
return delete_data;
}
}
实际使用
