數據結構

相互之間存在一種或多種特定關系的數據元素的集合

1.特定關系：

（1）邏輯結構：

①集合：所有在同一個集合中，關系平等。

②線性關系：數據和數據之間是一對一的關系。（數組是線性表的形式之一）

③樹狀關系：一對多

④圖狀解構：多對多

（2）物理結構（在內存當中的存儲關系，即將上述關系存入內存）：

①順序存儲：數據存放在連續的存儲單位中。邏輯關系和物理關系一致

②鏈式結構（鏈表）：數據存放的單位是隨機或任意的

Struct Per 數據元素

{

? ? ? ? char name;

? ? ? ? int age;

? ? ? ? char phone;

}

程序?=??數據?+?算法

2.算法：

①定義：是解決特定問題求解步驟的描述，計算機中表現為指令的有限序列，每條指令表示一個或多個操作。

②特征（函數）：

1），輸入，輸出特性，輸入時可選的，輸出時必須的。
2），有窮性，執行的步驟會自動結束，不能是死循環，并且每一步是在可以接受的時間內完成。
3），確定性，同一個輸入，會得到唯一的輸出。
4），可行性，每一個步驟都是可以實現的。

③設計：

1），正確性：語法正確
????????????????????合法的輸入能得到合理的結果。
? ? ? ? ? ? ? ? ? ? 對非法的輸入，給出滿足要求的規格說明
? ? ? ? ? ? ? ? ? ? 對精心選擇，甚至刁難的測試都能正常運行，結果正確
2），可讀性，便于交流，閱讀，理解
3），健壯性，輸入非法數據，能進行相應的處理，而不是產生異常
4），高效，存儲低，效率高?

④算法時間復雜度：執行算法所時間的度量，o（n）-粗略的估計

1）推算:???用常數1?取代運行時間中的所有加法常數
????????????????在修改后的運行函數中，只保留最高階項。
????????????????如果最高階存在且不是1，則取除這個項相乘的常數。

3.線代表

①定義：零個或多個數據元素的有限序列
②特征：元素之間是有順序了。如果存在多個元素，第一個元素無前驅，最有一個沒有后繼，其他的元素只有一個前驅和一個后繼。
?????????????? 當線性表元素的個數n（n>=0）定義為線性表的長度，當n=0時，為空表。在非空的表中每個元素都有一個確定的位置，如果a1是第一個元素，那么an就是第n個元素。

③線代表的常規操作：

線性表的常規操作??ADT
typedef?struct person?{
char?name[32];
char?sex;
int?age;
int?score;
}DATATYPE;
typedef?int?Datatype;
typedef?struct?list?{
DATATYPE?*head;
int?tlen;
int?clen;
}SeqList;

SeqList?*CreateSeqList(int?len);//創建順序鏈表
int?DestroySeqList(SeqList?*list);//銷毀鏈表
int?ShowSeqList(SeqList?*list);//遍歷輸出鏈表
int?InsertTailSeqList(SeqList?*list,?DATATYPE?data);//尾部元素賦值
int?IsFullSeqList(SeqList?*list);//判斷鏈表是否已滿
int?IsEmptySeqList(SeqList?*list);//判斷鏈表是否為空
int?InsertPosSeqList(SeqList?*list,?DATATYPE?data,?int?pos);//指定位置插入元素
int?FindSeqList(SeqList?*list,?char?*name);//查找元素
int?ModifySeqList(SeqList?*list,?char?*old,?DATATYPE?new);//修改成員值
int?DeleteSeqList(SeqList?*list,?char?*name);//刪除成員
int?ClearSeqList(SeqList?*list);//清空元素

④上述操作代碼表示:

#include "seqlist.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
SeqList *CreateSeqList (int len)//創建順序鏈表
{
? SeqList *sl = malloc (sizeof (SeqList));
? if (NULL == sl) {
? ? fprintf (stderr, "CreateSeqList malloc error\n");
? ? return NULL;
? }

? sl->head = malloc (sizeof (DATATYPE) * len);
? if (NULL == sl->head) {
? ? fprintf (stderr, "CreateSeqList malloc2 error\n");
? ? return NULL;
? }
? sl->tlen = len;
? sl->clen = 0;

? return sl;
}

int IsFullSeqList (SeqList *list)//判斷鏈表是否已滿
{
? if (NULL == list) {
? ? fprintf (stderr, "IsFullSeqList paramter error\n");
? ? return 1;
? }
? return list->clen == list->tlen;
}

int InsertTailSeqList (SeqList *list, DATATYPE *data)//尾部元素賦值
{
? if (IsFullSeqList (list)) {
? ? fprintf (stderr, "seqlist full\n");
? ? return 1;
? }

? memcpy (&list->head[list->clen], data, sizeof (DATATYPE));
? list->clen++;
? return 0;
}

int ShowSeqList (SeqList *list)//遍歷輸出鏈表
{
? int len = GetSizeSeqList (list);
? int i = 0;
? for (i = 0; i < len; ++i)
? {
? ? printf ("%s %c %d %d\n", list->head[i].name, list->head[i].sex,
? ? ? ? ? ? list->head[i].age, list->head[i].score);
? }
? return 0;
}

int GetSizeSeqList (SeqList *list)?
{?
? ? return list->clen;?
? ??
}

int FindSeqlist(SeqList *list,char *name)//查找元素
{
? int i = 0;
? int len = GetSizeSeqList(list);
? for(i = 0;i < len;++i)
? {
? ? if(0 == strcmp(list -> head[i].name,name))
? ? {
? ? ? return i;
? ? }

? }
? return -1;
}
int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos)//指定位插入元素
{
? if(IsFullSeqList(list))
? {
? ? return 1;
? }
? int len = GetSizeSeqList(list);
? if(pos < 0 || len < pos)
? {
?? ?return 1;
? }
? int i ;
? for(i = list -> clen;i > pos;--i)
? {
?? ?memcpy(&list -> head[i],&list -> head[i - 1],sizeof(DATATYPE));
? }
? memcpy(&list -> head[pos],data,sizeof(DATATYPE));
? list -> clen++;
? return 0;
}

int IsEmpList(SeqList *list)//判斷鏈表是否為空
{
?? ?return 0 == list -> clen;
}

int DeleteSeqList(SeqList *list,char *name)//刪除鏈表
{
?? ?if(IsEmpList(list))
?? ?{
?? ??? ?return 1;
?? ?}
?? ?int ret = FindSeqlist(list,name);
?? ?if(-1 == ret)
?? ?{
?? ??? ?return 1;
?? ?}
?? ?int len = GetSizeSeqList(list);
?? ?int i ;
?? ?for(i = ret;i < len - 1;++i)
?? ?{
?? ??? ?memcpy(&list -> head[i],&list -> head[i + 1],sizeof(DATATYPE));
?? ?}
?? ?list -> clen--;
?? ?return 0
? ｝