Binary
2 Mar 2020

线性表

线性表

👴只是想毕业

定义

n个具有相同特性的数据元素的有限序列

同一线性表中元素具有相同特性。

相邻数据元素之间存在序偶关系。

除第一个元素外，其它每一个元素有且仅有一个直接前驱。

除最后一个元素外，其它每一个元素有且仅有一个直接后继。

基本操作

MakeEmpty(L) 将L变为空表
Length(L) 返回表L的长度，即表中元素个数
Get(L，i) 返回L中位置i处的元素(1≤i≤n)
Prior(L，i) 返回i的前驱元素
Next(L，i) 返回i的后继元素
Locate(L，x) 返回元素x在L中的位置
Insert(L，i，x) 在表L的位置i处插入元素x，将原占据位置i的元素及后面的元素都向后推一个位置
Delete(L，p) 从表L中删除位置p处的元素
IsEmpty(L) 如果表L为空表(长度为0)则返回true，否则返回false
Clear(L) 清除所有元素
Init(L) 将L变为空表
Traverse(L) 遍历输出所有元素
Find(L，x) 查找并返回元素
Update(L，x) 修改元素
Sort(L) 对所有元素重新按给定的条件排序
strstr(string1,string2) 求string1中出现string2的首地址

龙鸣线性表

#include<stdio.h>
#include<stdlib.h>
#include <unistd.h>
typedef struct 
{
	char *data;
	int length;
	int listsize;
}list;


int read_int()
{
    char buf[8];
    read(0,buf,8);
    return atoi(buf);
}

void init(list *l, int size)
{
	l->data = (char *)malloc(size*sizeof(char));
	l->length = 0;
	l->listsize = size;
	if(l->data == NULL)
	{
		puts("gg");
		exit(1);
	}
	return;
}

void creat(list *l, int len)
{
	l->length = len;
	puts("input val:");
	for(int i = 0; i < l->length; ++i)
	{
		l->data[i] = read_int();
	}
	return;
}

void clear(list *l)
{
	free(l->data);
}

int get_length(list *l)
{
	return l->length;
}

int get(list *l, int index)
{
	if(index>=0 && index<l->length)
	{
		return l->data[index];
	}
	return -1;
}

int locate(list *l, int val)
{
	for(int i = 0; i < l->length; ++i)
	{
		if(l->data[i]==val)
		{
			return val;
		}
	}
	return -1;
}

int next(list *l, int index)
{
	if(index>=0 && index<l->length-1)
	{
		return l->data[index+1];
	}
	return -1;
}

int prior(list *l, int index)
{
	if(index>=1 && index<l->length)
	{
		return l->data[index-1];
	}
	return -1;
}

int insert(list *l, int val, int index)
{
	if(index<0 || index>l->length+1)
	{
		return -1;
	}
	if(l->length>=l->listsize)
	{
		l->data = realloc(l->data,(l->listsize+1)*sizeof(char));
		if(l->data == NULL)
		{
			puts("gg");
			exit(1);
		}
		l->listsize = l->listsize+1;
	}
	l->length += 1;
	for(int i = l->length; i >= index ; --i)
	{
		l->data[i+1] = l->data[i];
	}
	l->data[index] = val;

	return 0;
}

int delete(list *l, int index)
{
	if(index>=0 && index<l->length)
	{
		for(int i = index; i < l->length ; ++i)
		{
			l->data[i] = l->data[i+1];
		}
		l->data[l->length-1] = 0;
		l->length -= 1;
		return 0;
	}
	return -1;
}

int update(list *l, int index, int val)
{
	if(index>=0 && index<l->length)
	{
		l->data[index] = val;
		return 0;
	}
	return -1;
}

void show(list *l)
{
	for(int i = 0; i < l->length; ++i)
	{
		printf("%d ",l->data[i]);
	}
	puts("");
	return;
}
int main(int argc, char const *argv[]){
	list *p;
	list l;
	p = &l;
	return 0;
}

单链表

#include<stdio.h>
#include<stdlib.h>
#include <unistd.h>

typedef struct Node
{
	int data;
	struct Node *next;
}Node;

typedef int Status;

int read_int()
{
    char buf[8];
    read(0,buf,8);
    return atoi(buf);
}

Node* create_h(int n)
{
	Node *head;
	head = (Node*)malloc(sizeof(Node));
	Node *s;
	head->next = NULL;
	for (int i = 0; i < n; ++i)
	{
		s = (Node*)malloc(sizeof(Node));
		s->data = read_int();
		s->next =head->next;
		head->next = s;
	}
	return head;
}

Node* create_t(int n)
{
	Node *head;
	head = (Node*)malloc(sizeof(Node));
	Node *s;
	Node *tail;
	tail = head;
	head->next = NULL;

	for (int i = 0; i < n; ++i)
	{
		s = (Node*)malloc(sizeof(Node));
		s->data = read_int();
		tail->next=s;
		s->next = NULL;
		tail = s;

	}
	return head;
}



int get_length(Node *l)
{
	l = l->next;
	int len = 0;
	while(l != NULL)
	{
		len++;
		l = l->next;
	}
	return len;
}

Node* locate(Node *l, int index)
{
	if (index < 0 || index >= get_length(l))
	{
		return NULL;
	}
	l = l->next;
	for (int i = 0; i < index; ++i)
	{
		l = l->next;
	}
	return l;
}

Status insert(Node *l, int val, int index)
{
	Node *p = locate(l, index);
	if (p == NULL)
	{
		return 1;
	}
	Node *new = (Node*)malloc(sizeof(Node));
	new->data = val;
	new->next = p->next;
	p->next = new;
	return 0;

}

Status update(Node *l, int val, int index)
{
	Node *p = locate(l, index);
	if (p == NULL)
	{
		return 1;
	}
	p->data = val;
	return 0;

}

Status delete(Node *l, int index)
{
	Node *p = locate(l, index);
	if (p == NULL)
	{
		 return 1;
	}
	if (index == 0)
	{
		l->next = p->next;
		free(p);
		return 0;
	}
	Node *prev = locate(l, index-1);
	prev->next = p->next;

	free(p);
	return 0;
}

void show(Node *l)
{
	l = l->next;
	while(l != NULL)
	{
		printf("%d\n", l->data);
		l = l->next;
	}
	return;
}


int main(int argc, char const *argv[])
{
	
	//Node *p = create_h(3);
	Node *p = create_t(3);

	return 0;
}

双向链表

#include<stdio.h>
#include<stdlib.h>
#include <unistd.h>

typedef struct Node
{
	int data;
	struct Node *next;
	struct Node *prev;
}Node;

typedef int Status;

int read_int()
{
    char buf[8];
    read(0,buf,8);
    return atoi(buf);
}

Node* create_h(int n)
{
	Node *head;
	head = (Node*)malloc(sizeof(Node));
	Node *s;
	head->next = NULL;
	head->prev = NULL;
	for (int i = 0; i < n; ++i)
	{
		s = (Node*)malloc(sizeof(Node));
		s->data = read_int();
		s->next = head->next;
		s->prev = head;
		head->next = s;
	}
	return head;
}

Node* create_t(int n)
{
	Node *head;
	head = (Node*)malloc(sizeof(Node));
	Node *s;
	Node *tail;
	tail = head;
	head->next = NULL;
	head->prev = NULL;

	for (int i = 0; i < n; ++i)
	{
		s = (Node*)malloc(sizeof(Node));
		s->data = read_int();
		tail->next=s;
		s->prev = tail;
		s->next = NULL;
		tail = s;

	}
	return head;
}



int get_length(Node *l)
{
	l = l->next;
	int len = 0;
	while(l != NULL)
	{
		len++;
		l = l->next;
	}
	return len;
}

Node* locate(Node *l, int index)
{
	if (index < 0 || index >= get_length(l))
	{
		return NULL;
	}
	l = l->next;
	for (int i = 0; i < index; ++i)
	{
		l = l->next;
	}
	return l;
}

Status insert(Node *l, int val, int index)
{
	Node *p = locate(l, index);
	if (p == NULL)
	{
		return 1;
	}
	Node *new = (Node*)malloc(sizeof(Node));
	new->data = val;
	new->next = p->next;
	new->prev = p;
	p->next = new;
	return 0;

}

Status update(Node *l, int val, int index)
{
	Node *p = locate(l, index);
	if (p == NULL)
	{
		return 1;
	}
	p->data = val;
	return 0;

}

Status delete(Node *l, int index)
{
	Node *p = locate(l, index);
	if (p == NULL)
	{
		 return 1;
	}
	if (index == 0)
	{
		l->next = p->next;
		if (p->next != NULL)
		{
			p->next->prev = l;
		}
		free(p);
		return 0;
	}
	if (p->next != NULL)
	{
		p->next->prev = p->prev;
	}
	p->prev->next = p->next;
	free(p);
	return 0;
}

void show(Node *l)
{
	l = l->next;
	while(l != NULL)
	{
		printf("%d\n", l->data);
		l = l->next;
	}
	return;
}


int main(int argc, char const *argv[])
{
	
	//Node *p = create_h(3);
	//Node *p = create_t(3);

	return 0;
}
Tags:
0 comments



本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议（CC BY-NC-ND 4.0）进行许可。

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY-NC-ND 4.0).