【資料結構】資料結構學習大綱

資料結構概述

定義：

我們如何把現實中大量而複雜的問題以特定的資料類型和特定的存儲結構儲存到主存儲器（記憶體）中，以及在此基礎上為實作某個功能（比如查找某個元素，删除某個元素，對所有元素進行排序）而執行的相應操作，這個相應的操作也叫算法。

資料結構 = 個體 + 個體的關系

算法 = 對存儲資料的操作

算法：解題的方法和步驟

衡量算法的标準：

• 時間複雜度

  大概程式要執行的次數，而非執行的時間

• 空間複雜度

  算法執行過程中大概所占用的最大記憶體

• 難易程度
• 健壯性

預備知識：

1. 指針

位址：

• 位址就是記憶體單元的編号
• 從0開始的非負整數
• 範圍：0 —— FFFFFFF【0-4G-1】

指針：

指針就是位址，位址就是指針

指針變量是存放記憶體單元位址的變量

指針的本質是一個操作受限的非負整數

int *p;

&p==int **p;

2. 結構體

為什麼會出現結構體

• 為了表示一些複雜的資料，而普通的基本類型變量無法滿足要求

什麼叫結構體

• 結構體是使用者根據實際需要自己定義的複合資料類型

如何使用結構體

兩種方式：

struct Student st={1000,“zhangsan”,20};

struct Student *pst=&st;

1. st.sid

2. pst ->sid

   （pst所指向的結構體變量中的sid這個成員）

#include <stdio.h>
struct Student //struct Student是一種資料類型，包含sid、name、age三個成員
{
  int sid;
  char name[200];
  int age;
}; //分号不能省

int main()
{
  struct Student st={1000,"zhangsan",20}; //定義了一個變量st,包含學号、姓名、年齡三個成員資料
  printf("%d  %s  %d",st.sid,st.name,st.age); //用【結構體變量名.成員名】的方式輸出成員資料
  return 0;
}
           

int main()
{
  struct Student st ={1000,"zhangsan",20};
  // st.sid=99;//第一種方式
  
  struct Student *pst;
  pst=&st;  //第二種方式
  pst->sid=99; //pst->sid等價于(*pst).std  而(*pst).sid等價于st.sid,是以pst->sid等價于st.sid
}
           

注意事項

結構體變量不能加減乘除，但可以互相指派

普通結構體變量和結構體指針變量作為函數傳參的問題

3. 動态記憶體的配置設定和釋放

(這個部分好難T-T，聽的吃力）

#include <stdio.h>
#include <malloc.h>
int main()
{
  int a[5]={4,10,2,8,6};
int len;
printf("請輸入你需要配置設定的數組的長度：len=");
scanf("%d",&len);
int *pArr=(int *)malloc(sizeof(int)*len);
*pArr=4; //類似于a[0]=4
pArr[1]=10; //類似于a[1]=10;
printf("%d %d\n",*pArr,pArr[1]);
free(pArr); //把pArr所代表的動态配置設定的20個位元組的記憶體釋放
return 0;
}
           

資料結構

子產品一：線性結構

• 連續存儲 [數組]
• 離散存儲 [連結清單]
• 線性結構的兩種常見應用之一 棧
• 線性結構的兩種常見應用之一 隊列

專題：遞歸

1. 1+2+3…+100的和
2. 求階乘
3. 漢諾塔
4. 走迷宮

子產品二：非線性結構

• 樹
• 圖

子產品三：查找和排序

折半查找

排序：

• 冒泡
• 插入
• 選擇
• 快速排序
• 歸并排序

Java中容器和資料結構相關知識

Iterator接口

Map

哈希表